Longest Substring with At Most Two Distinct Characters

Medium
785.

Longest Substring with At Most Two Distinct Characters

Longest Substring with At Most Two Distinct Characters is a medium coding problem on strings, hash table and sliding window, asked in Amazon, Google and Flipkart interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstringTwoDistinct = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Longest Substring with At Most Two Distinct Characters Solution

Longest Substring with At Most Two Distinct Characters solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Longest Substring with At Most Two Distinct Characters is a medium coding problem on strings, hash table and sliding window, asked in Amazon, Google and Flipkart interviews.

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.

Hints for Longest Substring with At Most Two Distinct Characters

  1. Hint 1

    'At most two distinct' is monotone: shrinking a window never raises its distinct count.

  2. Hint 2

    Grow the window on the right; while it holds three distinct characters, shrink from the left.

  3. Hint 3

    A tally keyed by character tracks the distinct count in constant time.

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

  1. Keep a tally of characters in the window and a running distinct count.
  2. On adding s[r], bump its tally and raise the distinct count when it was absent.
  3. While the distinct count exceeds 2, drop s[l] and advance l, lowering the count when a tally reaches zero.
  4. 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

Java

public static int lengthOfLongestSubstringTwoDistinct(String s) {
    int[] cnt = new int[128];
    int distinct = 0, l = 0, best = 0;
    for (int r = 0; r < s.length(); r++) {
        if (cnt[s.charAt(r)]++ == 0) distinct++;
        while (distinct > 2) {
            if (--cnt[s.charAt(l)] == 0) distinct--;
            l++;
        }
        best = Math.max(best, r - l + 1);
    }
    return best;
}

C++

int lengthOfLongestSubstringTwoDistinct(string s) {
    vector<int> cnt(128, 0);
    int distinct = 0, l = 0, best = 0;
    for (int r = 0; r < (int) s.size(); r++) {
        if (cnt[(int) s[r]]++ == 0) distinct++;
        while (distinct > 2) {
            if (--cnt[(int) s[l]] == 0) distinct--;
            l++;
        }
        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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets