Skip to main content

340. Longest Substring with At Most K Distinct Characters

mediumAsked at Amazon

Given a string, return the length of the longest substring with at most k distinct characters. Amazon asks this to test whether you reach for sliding window with a char-frequency map.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Amazon loops.

  • Glassdoor (2026-Q1)— Amazon SDE II onsite reports cite this as a recurring sliding-window problem.
  • Blind (2025-09)— Recurring Amazon interview 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

Approaches

1. Sliding window with frequency map (optimal)

Expand right pointer. When distinct count exceeds k, shrink left until count <= k. Track max length.

Time
O(n)
Space
O(k)
function lengthOfLongestSubstringKDistinct(s, k) {
  if (k === 0) return 0;
  const counts = new Map();
  let left = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    counts.set(s[right], (counts.get(s[right]) || 0) + 1);
    while (counts.size > k) {
      const c = s[left];
      counts.set(c, counts.get(c) - 1);
      if (counts.get(c) === 0) counts.delete(c);
      left++;
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}

Tradeoff: Linear time. Each pointer moves forward, so total work is at most 2n. Map size bounded by k+1 during the shrink phase.

Amazon-specific tips

Amazon interviewers grade this on the sliding-window invariant. State out loud: 'I maintain a window [left, right] containing at most k distinct chars. Right always expands; left moves only to restore the invariant. Total work is linear because both pointers monotonically increase.' That framing is what they want to hear.

Common mistakes

  • Resetting the window on every iteration — O(n^2). The whole point of sliding window is to NEVER move left backward.
  • Forgetting to delete the char from the map when its count hits 0 (otherwise counts.size is wrong).
  • Off-by-one in the size of the current window (right - left + 1, inclusive on both ends).

Follow-up questions

An interviewer at Amazon may pivot to one of these next:

  • Longest Substring with At Most Two Distinct Characters (LC 159) — same pattern with k=2.
  • Longest Substring Without Repeating Characters (LC 3) — at most k=1 'duplicate.'
  • What if k could be huge but the alphabet were small (different optimization)?

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 is this O(n) and not O(nk)?

Both pointers move forward at most n times each. Each map operation is O(1) average. Total work is O(n).

What does 'distinct' mean in terms of the map?

counts.size = number of distinct chars in the current window. Adding a new char might increase it; removing the last occurrence of a char decreases it.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →