Two Pointer Sliding Window to Compute the Longest Substring with At Most Two Distinct Characters

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.

Longest Substring with At Most Two Distinct Characters using Sliding Window Algorithm

Let’s define a hash table to store the number of distinct characters in the current window. We can greedly expand the window to the right if it does not violate the requirement (at most two distinct characters). Then, for each iterations, if the current window has more than 2 distinct characters, we need to shrink from left side until it doesn’t.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        unordered_map<char, int> window;
        int left = 0, right = 0;
        int ans = 0;
        while (right < s.size()) {
            window[s[right]] ++;       
            while ((left <= right) && (window.size() &t; 2)) {
                if (-- window[s[left]] == 0) {
                    window.erase(s[left]);
                }
                left ++;
            }                      
            ans = max(ans, right - left + 1);
            right ++;
        }
        return ans;
    }
};

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        unordered_map<char, int> window;
        int left = 0, right = 0;
        int ans = 0;
        while (right < s.size()) {
            window[s[right]] ++;       
            while ((left <= right) && (window.size() &t; 2)) {
                if (-- window[s[left]] == 0) {
                    window.erase(s[left]);
                }
                left ++;
            }                      
            ans = max(ans, right - left + 1);
            right ++;
        }
        return ans;
    }
};

Then the size of the substring can be computed by its difference of two pointers i.e. left and right.

Longest Substring Algorithms

• Teaching Kids Programming – Longest Substring Without Repeating Characters – Another Version of Two Pointer / Sliding Window Algorithm
• Teaching Kids Programming – Divide and Conquer Algorithm to Find Longest Substring with Character Count of at Least K
• Teaching Kids Programming – Longest Substring with 2 Distinct Characters by Sliding Window Algorithm
• Compute Longest Substring with At Least K Repeating Characters via Divide and Conquer Algorithm
• Two Pointer Sliding Window to Compute the Longest Substring with At Most Two Distinct Characters
• Two Pointer with Sliding Window Algorithm to Compute the Longest Substring with At Most K Distinct Characters

–EOF (The Ultimate Computing & Technology Blog) —