DSA
340. Longest Substring with At Most K Distinct Characters
Covers: Brute Force O(n²), Sliding Window O(n). Classic premium sliding-window problem using a character frequency map.
Practice here
Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.
Example 1:
Input: s = "eceba", k = 2
Output: 3
Explanation: The substring is "ece" with length 3.
Example 2:
Input: s = "aa", k = 1
Output: 2
Explanation: The substring is "aa" with length 2.
Brute Force Approach#
Try every possible substring, track distinct character counts, and keep the longest one that satisfies the constraint.
Steps:
- Fix the start index i and expand j rightward.
- Maintain a frequency map for s[i..j].
- If the map's size exceeds k, break — extending j further only adds more characters.
- Otherwise, update maxLen.
- Clear the map and repeat for the next i.
class Solution {
public:
int lengthOfLongestSubstringKDistinct(string s, int k) {
int n = s.length();
int maxLen = 0;
for (int i = 0; i < n; i++) {
unordered_map<char, int> freq;
for (int j = i; j < n; j++) {
freq[s[j]]++;
// More than k distinct chars — no point extending further
if ((int)freq.size() > k) break;
maxLen = max(maxLen, j - i + 1);
}
}
return maxLen;
}
};
Time Complexity: O(n²) — TLE on large inputs
Space Complexity: O(k) — the map holds at most k+1 entries at any time
Optimal Solution: Sliding Window#
Instead of restarting from scratch for each i, keep a window [start, end] and shrink it from the left only when the distinct count exceeds k.
Key insight: when seenChars.size() > k after adding s[end], slide start rightward, decrementing counts and erasing the key when its count reaches 0 — that is what actually reduces seenChars.size().
Steps:
- Expand end across s, incrementing seenChars[s[end]].
- While seenChars.size() > k:
- Decrement seenChars[s[start]].
- If count hits 0, erase the key (so size() reflects reality).
- Advance start.
- After the while loop the window [start, end] is valid; update maxLen.
class Solution {
public:
int lengthOfLongestSubstringKDistinct(string s, int k) {
int n = s.length();
int start = 0, maxLen = 0;
unordered_map<char, int> seenChars;
for (int end = 0; end < n; end++) {
seenChars[s[end]]++;
while ((int)seenChars.size() > k) {
seenChars[s[start]]--;
if (seenChars[s[start]] == 0)
seenChars.erase(s[start]); // must erase so size() drops
start++;
}
maxLen = max(maxLen, end - start + 1);
}
return maxLen;
}
};
Time Complexity: O(n) — each character is added and removed from the map at most once
Space Complexity: O(k) — map holds at most k+1 entries before the shrink kicks in
Follow-up#
How would your logic change if k was very large and you needed to use a fixed-size array instead of a hash map?
When k is close to the alphabet size (e.g. 26 for lowercase letters, or 128 for ASCII), a hash map is heavier than necessary. You can swap it for a plain array:
class Solution {
public:
int lengthOfLongestSubstringKDistinct(string s, int k) {
int n = s.length();
int start = 0, maxLen = 0, distinct = 0;
vector<int> seenChars(256,0);
for(int end=0; end<n; end++){
if(seenChars[s[end]] == 0)
distinct++;
seenChars[s[end]]++;
while(distinct > k)
{
seenChars[s[start]]--;
if(seenChars[s[start]] == 0)
distinct--;
start++;
}
maxLen = max(maxLen, end-start+1);
}
return maxLen;
}
};
Trade-offs vs. the hash map version:
| unordered_map | int freq[128] | |
|---|---|---|
| Lookup | O(1) average (with hashing) | O(1) always (direct index) |
| Memory | Proportional to distinct chars seen | Fixed 128 ints (~512 B) |
| Cache behaviour | Scattered heap allocations | Single contiguous array — cache-friendly |
| Works for Unicode | ❌ (needs a wider map) | ❌ (only ASCII/Latin-1) |
The array approach is strictly faster in practice for ASCII input; stick with the map for Unicode or when the character domain is unknown.