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
PreviewThe 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…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse 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…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
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
To initialize the frequency map, left pointer, and result accumulator before scanning.
Expand Sliding Window and Track Character Frequencies
To iterate through the string with a right pointer, updating character counts and expanding the window.
Shrink Window to Maintain At Most K Distinct Characters
To move the left pointer forward while the window contains more than k distinct characters, updating counts accordingly.
Update Maximum Length of Valid Substring
To record the maximum window size seen so far that satisfies the constraint.
Return the Length of the Longest Valid Substring
To return the maximum length found after processing the entire string.
5 more steps with full analysis available on Pro.
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.
Full line-by-line criticality + rationale for all 15 lines available on Pro.
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?
See the answer with Pro.
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