[LeetCode] 159. Longest Substring with At Most Two Distinct Characters

Posted on | In

Problem

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

Example 1:

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

Example 2:

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

Explanation 1

  1. First, we can create a HashMap, and use it to store the key is the character, the value is the frequency of the character. Also, we initialize the left be 0. Iterate the input string and update the hashmap. While the hashmap has size greater than 2, then we need to decrease the frequency of character s[left] and increase left by 1. Also if the s[left]’s frequency is 0, we remove the key s[left] from the hashmap. Repeat these steps until the hashmap has size less than or equal to 2. Next, we update the result be max(res, i-left+1).

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        int res = 0;
        int left = 0;
        Map<Character, Integer> hm = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            char curChar = s.charAt(i);
            hm.put(curChar, hm.getOrDefault(curChar, 0)+1);
            while (hm.size() > 2) {
                char leftChar = s.charAt(left);
                hm.put(leftChar, hm.get(leftChar)-1);
                if (hm.get(leftChar) == 0) hm.remove(leftChar);
                left += 1;
            }

            res = Math.max(res, i-left+1);
        }

        return res;
    }
}

Explanation 2

  1. We can optimize the last solution by not using HashMap. First, we create two variables first means the first distince character, second means the second distince character. Also, we initialize curLen means the current 2 distinct character substring’s length, and cntSecond means the number of consecutive second characters.

  2. Iterate the input string’s characters. If the current character is the same as either character first or character second, we update curLen = curLen + 1, else, we update curLen = cntSecond + 1.

  3. Then, we try to update cntSecond. If the current character is the same as character second, then cntSecond = cntSecond + 1, else cntSecond = 1.

  4. Next, we try to update first and second. If the current character is not the same as second, then we update first be the original second and second be the current character.

  5. Next, we update the result res = max(res, curLen).

Solution 2

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) {
        int res = 0;
        int curLen = 0, cntSecond = 0;
        char first = ' ';
        char second = ' ';

        for (char c: s.toCharArray()) {
            curLen = (c == first || c == second) ? curLen + 1 : cntSecond + 1;
            cntSecond = (c == second) ? cntSecond + 1 : 1;
            if (c != second) {
                first = second;
                second = c;
            }
            res = Math.max(res, curLen);
        }

        return res;
    }
}