Skip to main content

340. Longest Substring With At Most K Distinct Characters

mediumAsked at Airbnb

Length of the longest substring of s with at most K distinct characters. Airbnb asks this right after LC 159 to see if you generalize the sliding-window template from 2 to K with no other code change.

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

Source citations

Public interview reports confirming this problem appears in Airbnb loops.

  • Glassdoor (2026-Q1)— Airbnb L4/L5 onsite reports list this as a recurring sliding-window medium, often paired with LC 159.
  • Blind (2025-12)— Recurring in Airbnb backend interview reports — generalization of LC 159.

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

Example 2

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

Approaches

1. Sliding window with count map (optimal)

Expand right adding to count map. When map size > k, shrink left until <= k.

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

Tradeoff: Same template as LC 159 with `2` replaced by `k`. Linear because each char enters and leaves at most once.

2. Sliding window with last-occurrence map (alternative)

Track the last index seen for each distinct char. When you'd exceed k, drop the char with the smallest last-index.

Time
O(n * k) worst case
Space
O(k)
function lengthOfLongestSubstringKDistinctAlt(s, k) {
  if (k === 0) return 0;
  const last = new Map();
  let l = 0, best = 0;
  for (let r = 0; r < s.length; r++) {
    last.set(s[r], r);
    if (last.size > k) {
      let minIdx = Infinity, minChar;
      for (const [c, i] of last) if (i < minIdx) { minIdx = i; minChar = c; }
      last.delete(minChar);
      l = minIdx + 1;
    }
    best = Math.max(best, r - l + 1);
  }
  return best;
}

Tradeoff: When you drop a char, jump left to past its last occurrence. The scan to find the minimum is O(k), so total is O(n*k). Cleaner for k small; the count-map version is O(n) total.

Airbnb-specific tips

Airbnb interviewers expect the LC 159 template generalized in one line — replace `2` with `k`. Articulate the same invariant: 'at most k distinct in the window'. If they ask follow-ups, mention the last-occurrence map variant and the tradeoff (O(n*k) vs O(n)).

Common mistakes

  • Forgetting the k=0 edge case (return 0).
  • Confusing 'at most k' with 'exactly k' — different problem.
  • Using a Set instead of a count Map.

Follow-up questions

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

  • Subarrays with K Different Integers (LC 992) — exactly-K via 'at most K minus at most K-1'.
  • Fruit Into Baskets (LC 904) — same problem hard-coded to k=2.
  • Longest Substring With At Least K Repeating Characters (LC 395) — different harder problem.

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 the count-map version O(n) total?

Each char index is visited exactly once by the right pointer and at most once by the left pointer. Both pointers only move forward.

When is the last-occurrence variant preferable?

When k is very small and finding the min-index char is cheap. For large k or general inputs, the count-map version is asymptotically better.

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 Airbnb interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →