Skip to main content

340. Longest Substring with At Most K Distinct Characters

mediumAsked at DoorDash

Given 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 Alex Chen, 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^4
  • 0 <= k <= 50

Examples

Example 1

Input
s = "eceba", k = 2
Output
3

Explanation: The substring is "ece" with length 3.

Example 2

Input
s = "aa", k = 1
Output
2

Explanation: 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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

Drill Longest Substring with At Most K Distinct Characters and other DoorDash interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →