Given a string s and an integer k, return the length of the longest substring that contains at most k distinct characters.
A substring is a continuous part of a string.
Return the maximum length of a substring in which the number of distinct characters is less than or equal to k.
Example 1
Input: s = "eceba", k = 2
Output: 3
Explanation: The longest substring with at most 2 distinct characters is "ece", so the answer is 3.
Example 2
Input: s = "aa", k = 1
Output: 2
Explanation: The longest substring with at most 1 distinct character is "aa", so the answer is 2.
Example 3
Input: s = "", k = 2
Output: 0
Explanation: The string is empty, so no substring can be formed.
Brute Force Approach
Every pair of start and end indices forms one possible substring. Checking every such range guarantees examination of every possible answer.
A fresh set can scan the selected range and record distinct characters. A substring remains valid when the set size stays at most k. Complete rescanning keeps the logic direct but repeatedly processes characters belonging to overlapping substrings.
Algorithm
Store the string length in
nand return0whenn == 0ork <= 0, because no non-empty valid substring can exist.Initialize
maxLength = 0to store the longest valid substring found so far.Select every
startindex and moveendfromstarttowardn - 1, so every possible substring can be examined.For each selected range
s[start...end], use a fresh set and scan the range to collect its distinct characters.If the set size exceeds
k, break the currentendtraversal, because extending the same starting position cannot remove any of the existing distinct characters.Otherwise, update
maxLengthwithend - start + 1, then return it after all starting positions are processed.
Dry Run
Longest Substring With At Most K Distinct Characters Brute Force Dry Run.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: // Counts distinct characters // inside the selected range. int countDistinct( const string& s, int start, int end ) { unordered_set<char> distinct; // Scan the selected substring. for (int i = start; i <= end; i++) { distinct.insert(s[i]); } return distinct.size(); }public: // Finds the longest substring // with at most k distinct characters. int longestSubstringAtMostKDistinct( string s, int k ) { int n = s.size(); // No valid non-empty substring // can exist in these cases. if (n == 0 || k <= 0) { return 0; } int maxLength = 0; // Try every possible start. for (int start = 0; start < n; start++) { // Extend the substring // from the current start. for (int end = start; end < n; end++) { int distinctCount = countDistinct(s, start, end); // Further expansion cannot // reduce the distinct count. if (distinctCount > k) { break; } maxLength = max( maxLength, end - start + 1 ); } } return maxLength; }};int main() { string s = "eceba"; int k = 2; Solution solution; cout << solution.longestSubstringAtMostKDistinct( s, k ) << endl; return 0;}Complexity Analysis
Time Complexity: O(N³), where N represents the string length. O(N²) substrings exist, and scanning one selected substring may require O(N) time.
Space Complexity: O(N), because the set may store every distinct character from one substring.
Better Approach
The Brute Force Approach first selects a complete substring and then scans the range separately. A better method builds each substring gradually from a chosen starting index.
A frequency map records characters during right-side expansion. After the map contains more than k distinct characters, every longer substring from the same start remains invalid because additional characters cannot remove an existing distinct character.
Algorithm
Store the string length in n and return 0 when n equals 0 or
k <= 0.Initialize maxLength with 0 for storing the best valid length found so far.
Select every start index and create a fresh frequency map, because each starting position begins an independent expansion.
Move end from start toward
n - 1and increase the frequency ofs[end]after adding the current character.Stop expansion when the map size exceeds k, because every longer substring from the same start will retain more than k distinct characters.
Update maxLength with
end - start + 1for every valid expansion, then return maxLength after processing all starting positions.
Dry Run
Longest Substring With At Most K Distinct Characters Better Appraoch Dry Run.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Expands from every start // while tracking frequencies. int longestSubstringAtMostKDistinct( string s, int k ) { int n = s.size(); // No valid non-empty substring // can exist in these cases. if (n == 0 || k <= 0) { return 0; } int maxLength = 0; // Try every possible start. for (int start = 0; start < n; start++) { unordered_map<char, int> frequency; // Grow the current substring. for (int end = start; end < n; end++) { frequency[s[end]]++; // Further expansion cannot // reduce the distinct count. if (frequency.size() > k) { break; } maxLength = max( maxLength, end - start + 1 ); } } return maxLength; }};int main() { string s = "eceba"; int k = 2; Solution solution; cout << solution.longestSubstringAtMostKDistinct( s, k ) << endl; return 0;}Complexity Analysis
Time Complexity: O(N²), where N represents the string length. Expansion from every starting position may process many later characters.
Space Complexity: O(N), because the frequency map may store many distinct characters for a general string.
Optimal Approach
Starting a new expansion from every position repeats earlier work. A sliding window keeps one active substring and reuses valid characters from the previous window.
Pointer right expands the window and explores longer substrings. When the distinct count exceeds k, pointer left removes characters until the window becomes valid again. Character frequencies reveal when a character has completely left the window and should no longer contribute to the distinct count.
Algorithm
Store the string length in n and return 0 when n equals 0 or
k <= 0.Initialize left and maxLength with 0, and create a frequency map for characters inside the current window.
Move right from 0 to
n - 1and increase the frequency ofs[right], because the current character enters the window.While the map contains more than k characters, decrease the frequency of
s[left], erase a zero-frequency entry, and move left forward.Update maxLength with
right - left + 1after restoring validity, because the current window now contains at most k distinct characters.Return maxLength after right processes every character.
Dry Run
Longest Substring With At Most K Distinct Characters Optimal Appraoch Dry Run.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Uses a sliding window // with character frequencies. int longestSubstringAtMostKDistinct( string s, int k ) { int n = s.size(); // No valid non-empty substring // can exist in these cases. if (n == 0 || k <= 0) { return 0; } unordered_map<char, int> frequency; int left = 0; int maxLength = 0; // Expand the window with right. for (int right = 0; right < n; right++) { frequency[s[right]]++; // Shrink until the window // has at most k distinct characters. while (frequency.size() > k) { frequency[s[left]]--; // Remove a character only // after its last copy leaves. if (frequency[s[left]] == 0) { frequency.erase(s[left]); } left++; } maxLength = max( maxLength, right - left + 1 ); } return maxLength; }};int main() { string s = "eceba"; int k = 2; Solution solution; cout << solution.longestSubstringAtMostKDistinct( s, k ) << endl; return 0;}Complexity Analysis
Time Complexity: O(N), where N represents the string length. Pointer right processes every character once, while pointer left moves only forward.
Space Complexity: O(N), because the frequency map may contain up to N distinct characters for a general character set. A fixed-size character set reduces auxiliary space to O(1).
FAQS
Q1. What is the difference between “at most K” and “exactly K” distinct characters?
“At most K” accepts any substring containing 0 through K distinct characters. “Exactly K” accepts only substrings containing K distinct characters.
Q2. Why can Better Approach expansion stop after exceeding K distinct characters?
Every longer substring from the same starting index retains all existing distinct characters, so later expansion cannot restore validity.
Q3. Why is a frequency map required in the Optimal Approach?
Character frequencies determine whether a character still remains after left-boundary removal. A zero frequency allows removal of the corresponding distinct entry.
Q4. Why does the window shrink through a while loop?
A single removal may not eliminate enough distinct characters. Repeated removal continues until the distinct count becomes at most K.
Q5. What happens when K exceeds the total distinct-character count of s?
The complete string satisfies the limit, so the answer equals the string length.
Q6. What result is returned when K equals zero?
No non-empty substring can contain zero distinct characters, so the answer equals 0.
Be the first to add a comment.