Longest Substring with At Most K Distinct Characters
Understanding the Problem
We need to find the longest contiguous section of the string where we use no more than k different characters. The substring must be contiguous, meaning we can't skip characters in the middle.
For example, in "eceba" with k = 2, the substring "ece" uses only two distinct characters ('e' and 'c'), and it's the longest such substring. The substring "eceb" wouldn't work because it has three distinct characters.
The key challenge is efficiently tracking how many distinct characters are in our current window. As we expand the window, new characters might push us over the limit, and we need to shrink from the other side until we're back within k distinct characters.
Key Constraints:
1 <= s.length <= 5 * 10^4→ With n up to 50,000, an O(n^2) brute force (checking all substrings) would mean up to 2.5 billion operations in the worst case, which is borderline. We should aim for O(n) or O(n log n) to be safe.0 <= k <= 50→ k can be zero, which means no characters are allowed, so the answer would be 0. Also, k is small (at most 50), which means hash map operations on the character frequency map are effectively O(1).sconsists of lowercase English letters → At most 26 distinct characters possible. If k >= 26, the answer is always the full string length.
Approach 1: Brute Force
Intuition
Check every possible substring, count its distinct characters, and keep track of the longest one that has at most k distinct characters.
For each starting position i, extend the substring to every possible ending position j, maintaining a set of characters seen so far. Once the set grows beyond k, stop extending from this starting point. Any longer substring starting at i contains this same set plus more, so it can only have more distinct characters, never fewer. Move on to the next start.
Algorithm
- Initialize
maxLengthto 0. - For each starting index
ifrom 0 to n - 1: - Create a set to track distinct characters in the current substring.
- For each ending index
jfromito n - 1: - Add
s[j]to the set. - If the set size exceeds
k, break out of the inner loop. - Otherwise, update
maxLength = max(maxLength, j - i + 1). - Return
maxLength.
Visualization and Code
Loading animation...
- Time Complexity: O(n^2). For each of the n starting positions, the inner loop can run up to n iterations. The early break helps in practice, but worst case is still quadratic.
- Space Complexity: O(k). The set holds at most k + 1 characters before we break. Since k <= 50, this is effectively constant space.
For each starting index, this re-scans a large portion of the string from scratch. The next approach keeps a single window and slides it forward instead of rebuilding it from each start.
Approach 2: Sliding Window with Hash Map (Optimal)
Intuition
The brute force restarts from scratch for every starting position, but most of the window is unchanged when the start moves forward by one. A sliding window reuses that work.
Maintain two pointers, left and right, defining the current window. Expand right to include more characters. Whenever the window has more than k distinct characters, shrink from left until it is back to at most k. At every valid state, track the maximum window length.
The supporting data structure is a hash map that tracks the frequency of each character in the current window. Adding a character (expanding right) increments its count. Removing a character (shrinking from left) decrements its count. When a count drops to zero, delete the key entirely, so the map size always equals the number of distinct characters in the window.
The sliding window relies on two properties of this problem. First, the substring must be contiguous, so a two-pointer window covers every valid candidate. Second, the constraint (at most k distinct characters) is monotonic: once a window has too many distinct characters, extending it on the right can only add more, never remove any. The single fix is to shrink from the left, which is why left never needs to move backward.
Both pointers only move forward. Each character is added to the window once (when right passes over it) and removed at most once (when left passes over it), so the total pointer movement is bounded by 2n and the algorithm runs in O(n).
Algorithm
- Initialize a hash map
charCountto track character frequencies, and setleft = 0,maxLength = 0. - Iterate
rightfrom 0 to n - 1: - Add
s[right]to the map (increment its count). - While the map has more than
kkeys (too many distinct characters): - Decrement the count of
s[left]in the map. - If the count reaches zero, remove
s[left]from the map. - Move
leftforward by one. - Update
maxLength = max(maxLength, right - left + 1). - Return
maxLength.
Visualization and Code
Loading animation...
- Time Complexity: O(n). Each character is processed at most twice: once when
rightincludes it and once whenleftexcludes it. The hash map operations (insert, delete, lookup) are O(1) amortized. - Space Complexity: O(k). The hash map stores at most k + 1 entries before we shrink. Since k <= 50, this is effectively constant space.
Approach 2 is optimal at O(n). The next approach is a variation that changes how the window shrinks: instead of moving left one step at a time, it tracks where each character last appeared and jumps left directly past the evicted character.
Approach 3: Sliding Window with Ordered Map
Intuition
Instead of moving left one step at a time, this approach jumps it directly to the position right after the evicted character.
Track the rightmost (most recent) index of each character in the window. When the window exceeds k distinct characters, find the character whose last occurrence is the smallest index, the one that appeared least recently. That character is removed entirely, and left jumps to one past its last occurrence. Every other tracked character has a last occurrence to the right of that index, so all of them remain inside the new window and the distinct count drops back to k.
Finding the minimum requires scanning the map, which holds at most k + 1 entries. So each eviction costs O(k) instead of the O(1) amortized step of Approach 2, giving O(n * k) overall. With k capped at 50 this stays fast, and the window collapses in a single jump rather than several increments.
Algorithm
- Initialize a hash map
lastSeenthat maps each character to its most recent index, and setleft = 0,maxLength = 0. - Iterate
rightfrom 0 to n - 1: - Record
lastSeen[s[right]] = right. - If the map has more than
kkeys: - Find the character with the smallest
lastSeenvalue (the one whose last occurrence is furthest left). - Set
leftto that value + 1 (jump past it). - Remove that character from the map.
- Update
maxLength = max(maxLength, right - left + 1). - Return
maxLength.
Visualization and Code
Loading animation...
- Time Complexity: O(n * k). We iterate through the string once with
right. For each step where we exceed k distinct characters, we scan the map (at most k + 1 entries) to find the minimum. Since k <= 50, this is effectively O(n). - Space Complexity: O(k). The map stores at most k + 1 entries.