Longest Substring with At Most K Distinct Characters
Problem
Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.
- 0 ≤ k ≤ 10⁵
- 0 ≤ s.length ≤ 10⁵
- s consists of ASCII characters
Example
s = "eceba", k = 23The longest substring with at most 2 distinct characters is "ece", which has length 3. The algorithm uses a sliding window to track character counts. Starting with the first character 'e', it expands the window to include 'c' and 'e' again, maintaining at most 2 distinct characters. When adding 'b' would exceed the limit, it shrinks the window from the left until the distinct count is back to 2. The maximum window length recorded during this process is 3.
Approach
Straightforward Solution
A brute-force approach would check every substring and count distinct characters, resulting in O(n^2) time complexity, which is inefficient for large inputs.
Core Observation
The problem requires finding the longest contiguous substring with a constraint on the number of distinct characters. This naturally suggests a sliding window approach that dynamically adjusts its boundaries to maintain the constraint.
Path to Optimal
The key insight is to use two pointers to represent a window and a hash map (or dictionary) to count characters within the window. Expand the right pointer to include new characters and update counts. When the number of distinct characters exceeds k, move the left pointer to shrink the window until the constraint is satisfied again. This approach ensures each character is visited at most twice, yielding O(n) time complexity.
Optimal Approach
Use a sliding window with two pointers and a dictionary to track character counts. Expand the right pointer to add characters, and shrink from the left when distinct characters exceed k. Track the maximum window size during this process. This guarantees O(n) time and O(k) space complexity.
Time
O(n)
Each character is visited at most twice: once when the right pointer expands the window and once when the left pointer shrinks it, resulting in linear time.
Space
O(k)
The dictionary stores counts of at most k distinct characters at any time, so space scales with k, which is at most the size of the input alphabet or k.
Pattern Spotlight
Sliding Window (Variable Size with Frequency Map)
Maintain a window that satisfies the problem's constraint by expanding the right pointer and contracting the left pointer only when the constraint is violated, using a frequency map to efficiently track the window's state.
Solution
| 1 | class Solution: |
| 2 | def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int: |
| 3 | if k <= 0 or not s: |
| 4 | return 0 |
| 5 | |
| 6 | counts = {} |
| 7 | left = 0 |
| 8 | res = 0 |
| 9 | |
| 10 | for right, ch in enumerate(s): |
| 11 | counts[ch] = counts.get(ch, 0) + 1 |
| 12 | |
| 13 | while len(counts) > k: |
| 14 | left_ch = s[left] |
| 15 | counts[left_ch] -= 1 |
| 16 | if counts[left_ch] == 0: |
| 17 | del counts[left_ch] |
| 18 | left += 1 |
| 19 | |
| 20 | res = max(res, right - left + 1) |
| 21 | |
| 22 | return res |
Step-by-Step Solution
Validate Input and Handle Edge Cases
| 3 | if k <= 0 or not s: |
| 4 | return 0 |
Objective
To immediately return 0 if k is zero or the input string is empty, as no valid substring can exist.
Key Insight
Checking for trivial or invalid inputs upfront prevents unnecessary computation and handles edge cases cleanly. If k is zero, no characters are allowed, so the longest substring length is zero. Similarly, an empty string has no substrings.
Interview Quick-Check
State & Boundaries
Return 0 immediately if k <= 0 or s is empty, as no valid substring can exist.
Common Pitfalls & Bugs
Failing to handle k=0 or empty string inputs can cause incorrect results or runtime errors.
Initialize Sliding Window State
| 6 | counts = {} |
| 7 | left = 0 |
| 8 | res = 0 |
Objective
To initialize the frequency map, left pointer, and result accumulator before scanning.
Key Insight
The frequency map tracks the window contents, left defines the window start, and res stores the best valid window length seen so far.
Interview Quick-Check
Core Logic
Initialize counts to track character frequencies in the window.
State & Boundaries
Initialize left and res to represent an empty window and no best answer yet.
Expand Sliding Window and Track Character Frequencies
| 10 | for right, ch in enumerate(s): |
| 11 | counts[ch] = counts.get(ch, 0) + 1 |
Objective
To iterate through the string with a right pointer, updating character counts and expanding the window.
Key Insight
By incrementing the count of the current character, the algorithm maintains an accurate frequency map of the window's contents. This allows quick checks on the number of distinct characters and supports efficient window adjustments.
Interview Quick-Check
Core Logic
Increment the count of the character at the right pointer to update the window's frequency map.
Complexity
Each character is processed once when expanding the window, contributing to O(n) time complexity.
Shrink Window to Maintain At Most K Distinct Characters
| 13 | while len(counts) > k: |
| 14 | left_ch = s[left] |
| 15 | counts[left_ch] -= 1 |
| 16 | if counts[left_ch] == 0: |
| 17 | del counts[left_ch] |
| 18 | left += 1 |
Objective
To move the left pointer forward while the window contains more than k distinct characters, updating counts accordingly.
Key Insight
Shrinking the window from the left removes characters and their counts, reducing the number of distinct characters. Deleting characters with zero count ensures the frequency map accurately reflects the window's state. This dynamic adjustment maintains the problem's constraint efficiently.
Interview Quick-Check
Core Logic
While the number of distinct characters exceeds k, decrement counts of the leftmost character and remove it if its count reaches zero, then move the left pointer forward.
State & Boundaries
The loop condition ensures the window always satisfies the constraint after shrinking.
Common Pitfalls & Bugs
Forgetting to remove characters with zero count from the map can cause incorrect distinct character counts.
Update Maximum Length of Valid Substring
| 20 | res = max(res, right - left + 1) |
Objective
To record the maximum window size seen so far that satisfies the constraint.
Key Insight
After adjusting the window to satisfy the constraint, the current window length is a candidate for the longest valid substring. Tracking the maximum ensures the final answer reflects the largest such window encountered during the iteration.
Interview Quick-Check
Core Logic
Update the result with the maximum of the current result and the current window size (right - left + 1).
Complexity
This constant-time update inside the loop maintains the global maximum efficiently.
Return the Length of the Longest Valid Substring
| 22 | return res |
Objective
To return the maximum length found after processing the entire string.
Key Insight
Returning the accumulated maximum length completes the solution, providing the length of the longest substring with at most k distinct characters.
Interview Quick-Check
State & Boundaries
Return the final result after the loop completes, representing the longest valid substring length.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
while len(counts) > k:While the window has more than k distinct characters, shrink it from the left.
This loop restores the invariant that the window contains at most k distinct characters by shrinking from the left until len(counts) <= k.
if counts[left_ch] == 0:Check whether the leftmost character has fully left the window.
A character stops contributing to the distinct count only when its frequency becomes zero, so this check is required for correctness.
del counts[left_ch]Remove the character from the map when its count reaches zero.
Deleting the zero-count key ensures len(counts) equals the true number of distinct characters, allowing the while condition to terminate correctly.
if k <= 0 or not s:Check if k is zero or the string is empty.
This early check handles edge cases where no valid substring can exist, preventing unnecessary computation and ensuring correctness.
return 0Return 0 immediately for invalid or trivial inputs.
Returning zero here correctly signals that no substring meets the criteria when k is zero or the string is empty.
counts = {}Initialize a dictionary to count characters in the current window.
This dictionary enables O(1) average-time updates and lookups of character frequencies, which is essential for efficient window management.
counts[ch] = counts.get(ch, 0) + 1Add the current character to the window state by incrementing its count.
Incrementing the frequency map maintains an accurate count of characters in the current window, enabling correct distinct-count checks.
counts[left_ch] -= 1Decrement the count of the leftmost character.
Decrementing reflects removing one occurrence of the leftmost character; this may eliminate a distinct character if the count hits zero.
left += 1Move the left pointer forward to complete one shrink step.
Advancing the left pointer actually shrinks the window boundary, pairing with the frequency updates to restore the constraint.
res = max(res, right - left + 1)Update the maximum valid window length found so far.
After the window is valid, its length is a candidate for the longest valid substring ending at right; taking the max preserves the best seen.
left = 0Initialize the left boundary of the sliding window.
The left pointer marks the start of the current window and moves forward to shrink the window when the distinct-count constraint is violated.
for right, ch in enumerate(s):Iterate over the string with the right pointer and current character.
The right pointer expands the window by scanning the string once, ensuring every character is considered as a window endpoint.
left_ch = s[left]Read the leftmost character that will be removed from the window.
Identifying the character leaving the window is necessary to correctly update its frequency as the left boundary advances.
res = 0Initialize the variable that tracks the maximum substring length found.
This accumulator stores the maximum valid window length encountered, ensuring the final return value is correct.
return resReturn the length of the longest substring with at most k distinct characters.
Returning the tracked maximum completes the algorithm and provides the required length of the longest valid substring.
Test Your Understanding
Why does shrinking the window from the left guarantee that the substring will again satisfy the 'at most k distinct characters' constraint?
Because removing characters from the left reduces the count of distinct characters, and once the count is at most k, the window satisfies the constraint again. Shrinking continues until this condition is met.
Related Problems
Sliding Window pattern
Don't just read it. Drill it.
Reconstruct Longest Substring with At Most K Distinct Characters from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Longest Substring with At Most K Distinct Characters drill