Longest Substring with At Most Two Distinct Characters

medium hash map string sliding window

Problem

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

Inputs = "eceba"

Output3

"ece" has 2 distinct chars and length 3.

def length_of_longest_substring_two_distinct(s):
    cnt = {}
    l = 0
    best = 0
    for r, ch in enumerate(s):
        cnt[ch] = cnt.get(ch, 0) + 1
        while len(cnt) > 2:
            cnt[s[l]] -= 1
            if cnt[s[l]] == 0:
                del cnt[s[l]]
            l += 1
        best = max(best, r - l + 1)
    return best

function lengthOfLongestSubstringTwoDistinct(s) {
  const cnt = new Map();
  let l = 0, best = 0;
  for (let r = 0; r < s.length; r++) {
    cnt.set(s[r], (cnt.get(s[r]) || 0) + 1);
    while (cnt.size > 2) {
      cnt.set(s[l], cnt.get(s[l]) - 1);
      if (cnt.get(s[l]) === 0) cnt.delete(s[l]);
      l++;
    }
    best = Math.max(best, r - l + 1);
  }
  return best;
}

class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        Map<Character, Integer> cnt = new HashMap<>();
        int l = 0, best = 0;
        for (int r = 0; r < s.length(); r++) {
            cnt.merge(s.charAt(r), 1, Integer::sum);
            while (cnt.size() > 2) {
                cnt.merge(s.charAt(l), -1, Integer::sum);
                if (cnt.get(s.charAt(l)) == 0) cnt.remove(s.charAt(l));
                l++;
            }
            best = Math.max(best, r - l + 1);
        }
        return best;
    }
}

int lengthOfLongestSubstringTwoDistinct(string s) {
    unordered_map<char, int> cnt;
    int l = 0, best = 0;
    for (int r = 0; r < (int)s.size(); r++) {
        cnt[s[r]]++;
        while ((int)cnt.size() > 2) {
            if (--cnt[s[l]] == 0) cnt.erase(s[l]);
            l++;
        }
        best = max(best, r - l + 1);
    }
    return best;
}

Explanation

This is the same sliding-window idea, fixed at at most two distinct characters. We grow a window and keep a count map; the number of distinct letters is just the map's size.

Each time the right pointer r adds a character, we bump its count. If the map ever holds more than two distinct keys, the window is invalid, so we slide the left pointer l forward.

While shrinking, we lower the count of the leaving character and remove its key entirely when the count reaches zero, which is what actually drops the distinct count back to two. After fixing the window we update best with its length r - l + 1.

Example: s = "eceba". The window reaches "ece" with distinct {e, c}, length 3. Adding b makes three distinct, so the left side shrinks. The longest valid window is length 3.

Every character is added once and removed at most once, so the algorithm is linear time and uses only constant extra space.

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