159. Longest Substring with At Most Two Distinct Characters

Sliding Window

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
class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        int[] count = new int[128];

        int i = 0, maxLength = 0, distinctCharCount = 0;
        for (int j = 0; j < s.length(); j++) {
            char c = s.charAt(j);

            // 不重复字符已经达到两个且 c 是一个新的字符
            while (distinctCharCount == 2 && count[c] == 0) {
                char leftmost = s.charAt(i);
                if (--count[leftmost] == 0) {
                    distinctCharCount--;
                }
                i++;
            }

            if (count[c]++ == 0) {
                distinctCharCount++;
            }

            maxLength = Math.max(maxLength, j - i + 1);
        }

        return maxLength;
    }
}

Sliding Window

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) {
        Map<Character, Integer> charToLastIndexMap = new HashMap<>();

        int i = -1, maxLength = 0;
        for (int j = 0; j < s.length(); j++) {
            char c = s.charAt(j);
            if (charToLastIndexMap.size() == 2 && !charToLastIndexMap.containsKey(c)) {
                // 当前为第三个不同的字符
                i = Collections.min(charToLastIndexMap.values());
                charToLastIndexMap.remove(s.charAt(i));
            }

            maxLength = Math.max(maxLength, j - i);
            charToLastIndexMap.put(c, j);
        }

        return maxLength;
    }
}

References

159. Longest Substring with At Most Two Distinct Characters