340. Longest Substring with At Most K Distinct Characters
mediumAsked at DoorDashGiven a string and an integer k, return the length of the longest substring with at most k distinct characters. DoorDash uses this as a sliding-window template — they want a clean expand-shrink pattern with a count map.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in DoorDash loops.
- Glassdoor (2026-Q1)— DoorDash SWE onsite reports cite this as a recurring sliding-window template.
- Blind (2025-12)— DoorDash new-grad reports note this as a backend Round 2 question.
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.
Constraints
1 <= s.length <= 5 * 10^40 <= k <= 50
Examples
Example 1
s = "eceba", k = 23Explanation: The substring is "ece" with length 3.
Example 2
s = "aa", k = 12Explanation: The substring is "aa" with length 2.
Approaches
1. Sliding window with count map (optimal)
Expand right; on count > k, shrink left until count == k. Track max window length.
- Time
- O(n)
- Space
- O(k)
function lengthOfLongestSubstringKDistinct(s, k) {
if (k === 0) return 0;
const count = new Map();
let left = 0;
let best = 0;
for (let right = 0; right < s.length; right++) {
count.set(s[right], (count.get(s[right]) || 0) + 1);
while (count.size > k) {
count.set(s[left], count.get(s[left]) - 1);
if (count.get(s[left]) === 0) count.delete(s[left]);
left++;
}
if (right - left + 1 > best) best = right - left + 1;
}
return best;
}Tradeoff: DoorDash's preferred answer. Amortized O(n) — each char enters and leaves the window once. Map size never exceeds k+1 transiently.
2. Brute force
For every starting index, extend right until distinct count exceeds k. Track max.
- Time
- O(n * k)
- Space
- O(k)
function bruteKDistinct(s, k) {
if (k === 0) return 0;
let best = 0;
for (let i = 0; i < s.length; i++) {
const count = new Map();
for (let j = i; j < s.length; j++) {
count.set(s[j], (count.get(s[j]) || 0) + 1);
if (count.size > k) break;
best = Math.max(best, j - i + 1);
}
}
return best;
}Tradeoff: Easier to derive. Within constraints (k <= 50, n = 5*10^4) it works but is wasteful. Sliding window is the canonical answer.
DoorDash-specific tips
DoorDash interviewers grade on the SLIDING WINDOW TEMPLATE. State: 'expand right; when invariant breaks, shrink left until restored.' That sentence covers an entire class of problems and shows you've seen the pattern.
Common mistakes
- Forgetting to delete the entry from the map when count drops to 0 — corrupts the size check.
- Using a Set instead of a Map — can't track per-char counts for the shrink step.
- Off-by-one on window length — it's right - left + 1.
Follow-up questions
An interviewer at DoorDash may pivot to one of these next:
- Longest Substring with At Most Two Distinct Characters (LC 159) — k = 2.
- Subarrays with K Different Integers (LC 992) — count subarrays, not max length.
- Fruit Into Baskets (LC 904) — same shape, real-world framing.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why amortized O(n)?
Each character enters the window once (via right) and leaves at most once (via left). So total work is O(2n) = O(n).
Why use Map (not object) for the count?
Map is O(1) and never collides on non-string keys. For string keys both work, but Map is cleaner.
Free learning resources
Curated free links for this problem.