Longest Substring with At Most Two Distinct Characters (LC 159) — Variable Sliding Window

Problem Statement#

LeetCode 159 — Longest Substring with At Most Two Distinct Characters (Hard)

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.

Example 1:

Input:  s = "eceba"
Output: 3
Explanation: The substring "ece" has 2 distinct characters and length 3.
             "eceb" has 3 distinct characters, which exceeds the limit.

Example 2:

Input:  s = "ccaabbb"
Output: 5
Explanation: The substring "aabbb" has 2 distinct characters (a, b) and length 5.
             "ccaabbb" has 3 distinct characters.

Example 3:

Input:  s = "a"
Output: 1
Explanation: Single character string, trivially valid.

Why This Problem Matters#

This is a premium LeetCode problem that Google, Meta, and Amazon ask in phone screens. It is the natural generalization bridge between LC 3 (no repeating characters) and LC 340 (at most k distinct), making it a critical stepping stone in the sliding window curriculum. The pattern — expand right, shrink left when constraint violated, track state in a frequency map — is reusable verbatim for at-most-k-distinct and many other window-constraint problems.

In practice, the "at most 2 distinct" constraint models real problems: finding the longest contiguous time period in a log where only two services were active, the longest genomic sequence with at most two nucleotide types, or the longest trading session dominated by at most two asset classes. The O(n) solution is the expected answer; anything quadratic will fail at 10^5 length.

The Core Insight#

Use a variable-size sliding window with two pointers left and right. Expand right to include new characters. Maintain a frequency map counting how many times each character appears in the current window. When the map has more than 2 keys (i.e., 3 or more distinct characters), shrink from the left: decrement the count of s[left], remove it from the map if its count hits 0, then advance left. At every step, the window [left, right] satisfies the constraint.

The key efficiency insight: instead of recomputing distinct counts from scratch each time, the map size tells us the number of distinct characters in O(1). Insertion and deletion from a hash map are O(1) amortized, so the entire algorithm is O(n).

The answer is the maximum window length seen across all valid positions of right.

Visual Dry Run#

Input: s = "eceba"

Maximum length seen = 3 ("ece"). Answer = 3.

Common Mistakes#

1. Using a set instead of a frequency map. A set tracks distinct characters correctly during expansion, but when you remove s[left] from the window, you cannot know whether the character still appears elsewhere in the window without scanning — which is O(n). A frequency map solves this in O(1).

2. Deleting the character from the map at the wrong time. Only delete a character from the map when its count reaches exactly 0, not before. Deleting at count 1 (before decrement) or after re-adding incorrectly inflates/deflates the distinct count.

3. Not moving left far enough. When 3 distinct characters are present, you must keep shrinking left until the window is valid again (map size <= 2). A single if instead of a while loop can leave the window invalid for multiple steps.

4. Initializing ans = 0 and returning 0 for empty strings. The constraints guarantee s.length >= 1, so ans = 0 is fine as a starting value — but if you forget to update it inside the loop (e.g., only update after the shrink), you might miss recording the window length.

5. Hardcoding 2 instead of parameterizing k. The interviewer will almost certainly ask "what if it were k distinct instead of 2?" If your code hardcodes the constant, you cannot generalize easily. Write it with a variable k = 2 so the change is trivial.

6. Using O(n) inner loops to find which character to evict. Some candidates scan the window to find the character that appears earliest (to evict it). This makes the algorithm O(n²). The frequency map + advancing left one step at a time is the correct O(n) approach.

7. Returning right - left instead of right - left + 1. The window from index left to right inclusive has right - left + 1 characters. Off-by-one is a common final-step error.

Solutions#

Python#

from collections import defaultdict
 
def lengthOfLongestSubstringTwoDistinct(s: str) -> int:
    # freq maps each character to its count in the current window
    freq = defaultdict(int)
    left = 0    # left boundary of the sliding window
    ans = 0     # track the maximum valid window length
 
    for right in range(len(s)):
        # Expand: include s[right] in the window
        freq[s[right]] += 1
 
        # Shrink: while more than 2 distinct characters are present,
        # move the left pointer rightward and reduce counts
        while len(freq) > 2:
            freq[s[left]] -= 1          # remove one occurrence of s[left]
            if freq[s[left]] == 0:
                del freq[s[left]]       # character fully evicted from window
            left += 1                   # advance left boundary
 
        # Window [left, right] now has at most 2 distinct characters
        ans = max(ans, right - left + 1)
 
    return ans

JavaScript#

var lengthOfLongestSubstringTwoDistinct = function(s) {
    // freq maps character -> count within the current window
    const freq = new Map();
    let left = 0;   // left boundary of the sliding window
    let ans = 0;    // maximum valid window length seen so far
 
    for (let right = 0; right < s.length; right++) {
        const c = s[right];
 
        // Expand: add s[right] to the window
        freq.set(c, (freq.get(c) || 0) + 1);
 
        // Shrink: while the window has more than 2 distinct characters,
        // evict from the left one character at a time
        while (freq.size > 2) {
            const leftChar = s[left];
            freq.set(leftChar, freq.get(leftChar) - 1);  // decrement count
            if (freq.get(leftChar) === 0) {
                freq.delete(leftChar);   // fully remove evicted character
            }
            left++;   // advance left boundary
        }
 
        // Record the valid window length
        ans = Math.max(ans, right - left + 1);
    }
 
    return ans;
};

Complexity Analysis#

Space is O(1) in practice because the map holds at most 3 entries (2 valid + 1 that triggers the shrink). For the general k-distinct version, space is O(k).

Follow-up Questions#

1. Generalize to at most k distinct characters (LC 340). Replace the constant 2 with k in the while len(freq) > k condition. Everything else stays identical. O(n) time, O(k) space.

2. What if you need exactly 2 distinct characters? Use the formula: exactly(k) = atMost(k) - atMost(k-1). Run the sliding window twice. This pattern solves LC 992 (Subarrays with K Different Integers).

3. What if the string contains Unicode characters? Replace the fixed-size array (if you were using one) with a hash map. The frequency map approach here already handles arbitrary character sets.

4. Can you solve this without a hash map using just two variables? For exactly 2 distinct characters in a specific structure, there are tricks using the last-seen indices of two tracked characters. But the hash map approach generalizes cleanly to k distinct without modification.

5. What is the longest substring with no repeating characters (LC 3)? Same sliding window pattern, but the constraint is that every character in the window has frequency exactly 1. The map is still used; eviction happens when freq[s[right]] > 1 after inserting.

This Pattern Solves#

• LC 159 — Longest Substring with At Most Two Distinct Characters (this problem)
• LC 340 — Longest Substring with At Most K Distinct Characters (generalization)
• LC 3 — Longest Substring Without Repeating Characters (k=1, strict uniqueness)
• LC 992 — Subarrays with K Different Integers (atMost(k) - atMost(k-1))
• LC 904 — Fruit Into Baskets (at most 2 distinct values — same problem reworded)

Key Takeaway#

The expand-right, shrink-left sliding window with a frequency map is the canonical tool for "longest substring with at most X distinct characters." The map size gives the distinct count in O(1). Always delete from the map when a count hits zero — that is what keeps the distinct count accurate. Parameterize the constraint as k from the start; the generalization is trivial, and interviewers always ask for it.

Key Takeaways#

• LC 159 (at most 2 distinct) and LC 340 (at most k distinct) use the same expand-right, shrink-left sliding window with a frequency map — parameterize k from the start.
• The distinct count is len(freq_map) (or freq_map.size in JS): O(1) per step, no need to recount the window.
• Delete a character from the map only when its count drops to zero — that is the only event that reduces the distinct count.
• Shrink from the left while len(freq) > k: decrement freq[s[left]], delete if zero, advance left.
• Record ans = max(ans, right - left + 1) after every expand step (not just after shrinking), because the window may already be valid.
• LC 904 (Fruit Into Baskets) is word-for-word the same problem with k = 2 — the solution is identical.
• For exactly-k-distinct problems (LC 992), use the formula atMost(k) - atMost(k-1): run the at-most window twice and subtract.