159. Longest Substring with At Most Two Distinct Characters

发表于 | 分类于

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

For example, Given s = “eceba”,

T is “ece” which its length is 3.

解法1：O(N)

这题是sliding window的一个例题。要掌握一下模板。这题和另一题at most k distinct characters的解法一致。
主要的思路就是维护一个hashmap存取每一个元素出现的次数，如果为１的话，就说明是新入的元素，总个数要＋１
同时维护一个start指针来标记左面的边界，每次找到一个符合标准的答案时，更新最长的长度。
C++

1

Java

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
public class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        int count = 0, start = 0, end = 0;
        int res = 0;
        while (end < s.length()) {
            char current = s.charAt(end);
            map.put(current, map.getOrDefault(current, 0) + 1);
            if (map.get(current) == 1) {
                // new character
                count++;
            }
            end++;  // move end 1 position forward
            while (count > 2) {
                char prev = s.charAt(start);
                map.put(prev, map.get(prev) -1 );
                if (map.get(prev) == 0) {
                    // Removed one character
                    count--;
                }
                start++;
            }
            res = Math.max(res, end - start);
        }
        return res;
    }
}