159. Longest Substring with At Most Two Distinct Characters

• Difficulty: Hard

• Topics: Hash Table, Two Pointers, String, Sliding Window

• Similar Questions:

  • Longest Substring Without Repeating Characters

  • Sliding Window Maximum

  • Longest Substring with At Most K Distinct Characters

  • Subarrays with K Different Integers

Problem:

Given a string s , find the length of the longest substring t  that contains at most 2 distinct characters.

Example 1:

Input: "eceba"
Output: 3
Explanation: t is "ece" which its length is 3.

Example 2:

Input: "ccaabbb"
Output: 5
Explanation: t is "aabbb" which its length is 5.

Solutions:

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        unordered_map<char, int> charCount;
        int left = 0;
        int maxLen = 0;

        for (int right = 0; right < s.length(); ++right) {
            ++charCount[s[right]];
            if (charCount.size() <= 2) {
                maxLen = max(maxLen, right - left + 1);
            } else {
                while (left <= right && charCount.size() > 2) {
                    if(--charCount[s[left]] == 0)  charCount.erase(s[left]);
                    ++left;
                }
            }
        }

        return maxLen;
    }
};