Longest Substring with At Most Two Distinct Characters — Medium Problem & Solution

Return the length of the longest substring of s that contains at most two distinct characters.

Difficulty: Medium
Topics: Strings, Hash Table, Sliding Window
Asked at: Amazon, Google, Flipkart
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Return the length of the longest substring of s that contains at most two distinct characters.

Example 1

Input: s = "codekairo"
Output: 2
Explanation: Every character differs from its neighbours, so no window of three works.

Example 2

Input: s = "eceba"
Output: 3
Explanation: "ece" uses only e and c.

Example 3

Input: s = "ccaabbb"
Output: 5
Explanation: "aabbb".

Constraints

1 <= s.length <= 100000
s consists of English letters.

How to solve Longest Substring with At Most Two Distinct Characters

The classic variable-size window. Extend the right edge one character at a time and repair the invariant by pulling the left edge in while there are more than two distinct characters.

Approach

Keep a tally of characters in the window and a running distinct count.
On adding s[r], bump its tally and raise the distinct count when it was absent.
While the distinct count exceeds 2, drop s[l] and advance l, lowering the count when a tally reaches zero.
Record the window's length after each repair.

Why it works

Because the predicate is monotone in the left edge, for every right edge the valid left edges form a suffix, so l never needs to move backwards. Each index enters and leaves the window once, giving a linear scan.

Complexity

Time — O(n)
Space — O(1) — at most three tallies live at once

Pitfalls

Dropping an entry from the tally without checking it reached zero loses track of the distinct count.
Measuring the window before the shrink loop counts an invalid window.
A window of one character is always valid, so the answer is at least 1.

Reference solution

Python

def lengthOfLongestSubstringTwoDistinct(s: str) -> int:
    cnt = {}
    distinct = 0
    l = 0
    best = 0
    for r, c in enumerate(s):
        cnt[c] = cnt.get(c, 0) + 1
        if cnt[c] == 1:
            distinct += 1
        while distinct > 2:
            u = s[l]
            cnt[u] -= 1
            if cnt[u] == 0:
                distinct -= 1
            l += 1
        best = max(best, r - l + 1)
    return best

JavaScript

var lengthOfLongestSubstringTwoDistinct = function(s) {
    var cnt = {};
    var distinct = 0, l = 0, best = 0;
    for (var r = 0; r < s.length; r++) {
        var c = s.charAt(r);
        cnt[c] = (cnt[c] || 0) + 1;
        if (cnt[c] === 1) distinct++;
        while (distinct > 2) {
            var u = s.charAt(l);
            cnt[u]--;
            if (cnt[u] === 0) distinct--;
            l++;
        }
        if (r - l + 1 > best) best = r - l + 1;
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue