159. Longest Substring with At Most Two Distinct Characters

Posted on Edited on In

159. Longest Substring with At Most Two Distinct Characters

Description

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

Example 1:

1
2
3
Input: s = "eceba"
Output: 3
Explanation: The substring is "ece" which its length is 3.

Example 2:

1
2
3
Input: s = "ccaabbb"
Output: 5
Explanation: The substring is "aabbb" which its length is 5.

Constraints:

  • 1 <= s.length <= 10^5
  • s consists of English letters.

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        int num_distinct = 0, left = 0, right = 0, res = 0, n = s.size();
        int count[52]{};
        while (right < n) {
            int idx = getIndex(s[right]);
            if (count[idx] == 0) {
                num_distinct++;
            }
            count[idx]++;
            while (num_distinct > 2) {
                int l_idx = getIndex(s[left]);
                count[l_idx]--;
                if (count[l_idx] == 0) {
                    num_distinct--;
                }
                left++;
            }
            res = max(res, right - left + 1);
            right++;
        }
        return res;
    }

    int getIndex(char& c) {
        if (isupper(c)) {
            return c - 'A' + 26;
        } else {
            return c - 'a';
        }
    }
};