Longest Substring with At Most K Distinct Characters
Asked at TikTok
Problem
Longest Substring with At Most K Distinct Characters asks for the length of the longest substring that contains no more than k different characters. It is the canonical variable-size sliding window problem: grow the window greedily and shrink it only when a constraint breaks.
Asked At
| Company | Difficulty | |
|---|---|---|
| TikTok | Medium | View all TikTok questions → |
How to Think About It
Brute force checks every substring and counts its distinct characters: O(n²) or worse.
Key insight: if a window has too many distinct characters, every larger window that contains it also does. So when the constraint breaks, you can safely move the left edge forward instead of restarting.
Keep a hash map of character counts inside the window [left, right]. Add s[right]; while the map has more than k keys, decrement s[left] (deleting it at zero) and move left right.
After fixing the window, right - left + 1 is a valid length — track the maximum.
Walkthrough for "eceba", k = 2: e,ec,ece (len 3) -> add b: 3 distinct, shrink until "eb" -> add a: shrink to "ba". Answer 3.
Optimal Approach
Step 1: count = {}, left = 0, best = 0.
Step 2: For each right:
count[s[right]] += 1
While len(count) > k:
count[s[left]] -= 1; delete it if it hits 0; left += 1.
best = max(best, right - left + 1).
Step 3: Return best.
Each character enters and leaves the window at most once.
Time: O(n). Space: O(k).
What Trips People Up in Real Interviews
Not deleting keys whose count drops to zero. Then len(count) overstates the distinct characters and the window shrinks too much.
Restarting the window from scratch when the constraint breaks. That makes it quadratic; only move left forward.
Forgetting k = 0, where the answer is 0.
Using an if instead of a while to shrink. One removal may not be enough to get back to k distinct characters.
Solution Code
def lengthOfLongestSubstringKDistinct(s, k):
count = {}
left = best = 0
for right, ch in enumerate(s):
count[ch] = count.get(ch, 0) + 1
while len(count) > k:
c = s[left]
count[c] -= 1
if count[c] == 0:
del count[c]
left += 1
best = max(best, right - left + 1)
return bestFrequently Asked Questions
What is the Longest Substring with At Most K Distinct Characters problem?
Longest Substring with At Most K Distinct Characters asks for the length of the longest substring that contains no more than `k` different characters. It is the canonical variable-size sliding window problem: grow the window greedily and shrink it only when a constraint breaks.
How do you solve Longest Substring with At Most K Distinct Characters?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Longest Substring with At Most K Distinct Characters?
Longest Substring with At Most K Distinct Characters is asked at TikTok. It is a medium difficulty problem.
What are common mistakes on Longest Substring with At Most K Distinct Characters?
- Not deleting keys whose count drops to zero. Then `len(count)` overstates the distinct characters and the window shrinks too much.
- Restarting the window from scratch when the constraint breaks. That makes it quadratic; only move `left` forward.
- Forgetting `k = 0`, where the answer is 0.
- Using an `if` instead of a `while` to shrink. One removal may not be enough to get back to `k` distinct characters.