159. Longest Substring With At Most Two Distinct Characters

mediumAsked at Airbnb

Find the length of the longest substring of s containing at most two distinct characters. Airbnb asks this as the sliding-window-with-count template they'll generalize to K in the follow-up.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-19

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.
Blind (2025-11)— Recurring in Airbnb backend interview reports — pairs with LC 340 follow-up.

Problem

Given a string s, return the length of the longest substring that contains at most two distinct characters.

Constraints

1 <= s.length <= 10^5
s consists of English letters.

Examples

Example 1

Input

s = "eceba"

Output

Explanation: "ece" has 2 distinct chars and length 3.

Example 2

Input

s = "ccaabbb"

Output

Explanation: "aabbb" has 2 distinct chars and length 5.

Approaches

1. Brute-force enumerate substrings

For every (i, j), count distinct chars in s[i..j]; track max length with <= 2 distinct.

Time: O(n^3)
Space: O(n)

function lengthOfLongestSubstringTwoDistinctBrute(s) {
  let best = 0;
  for (let i = 0; i < s.length; i++) {
    const seen = new Set();
    for (let j = i; j < s.length; j++) {
      seen.add(s[j]);
      if (seen.size > 2) break;
      best = Math.max(best, j - i + 1);
    }
  }
  return best;
}

Tradeoff: Quadratic with the early break. Mention as a baseline, then pivot to sliding window.

2. Sliding window with count map (optimal)

Expand right adding chars to a count map. When map size > 2, shrink left until back to 2.

Time: O(n)
Space: O(1)

function lengthOfLongestSubstringTwoDistinct(s) {
  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 > 2) {
      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: Each char enters and leaves the window once — linear total work. Constant extra space because the map has at most 3 entries at any time.

Airbnb-specific tips

Airbnb's bar is naming the sliding-window invariant: 'I maintain a window with at most 2 distinct chars by counting frequencies. When a new char makes that 3, I shrink left until one of them drops to 0.' This is the same template as the K-distinct follow-up; mentioning the generalization shows depth.

Common mistakes

Using a Set instead of a count Map — Set can't tell you when to remove a char from the window.
Decrementing count without deleting when it hits 0 — map.size stays inflated.
Off-by-one on the window bounds (best = r - l + 1).

Follow-up questions

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

Longest Substring With At Most K Distinct Characters (LC 340) — replace 2 with K.
Longest Substring Without Repeating Characters (LC 3) — same template, different constraint.
Longest Repeating Character Replacement (LC 424) — variant with replacement budget.

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 space O(1)?

The count map holds at most 3 keys at any time (before shrinking back to 2). Three is a constant.

Why a sliding window and not DP?

The optimal substring property here is contiguous, and shrinking from left maintains the invariant without restarting. DP would compute redundant subproblems.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Longest Substring With At Most Two 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 →