Longest Substring with At Most Two Distinct Characters leetcode

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.

创建一个hashmap, key存字母 value存字母最后出现时候的下角标.

如果新的字母在表中已经有了, 更新下角标就可以. 或者hashmap存储量不达到两个 把新字母放入map

如果新字母不包含在map中且map的存储量已经达到了两个, 首先更新maxL. 然后就要找map中存储的value中数值最小一个并在map中除去, 更新start的位置, 放入新的字母.

最后遍历完毕, 还要跟s.length() - start 比较
如果题目是k个不同character 只需把map.size() > 2 换成k就可以

时间O(n)

public class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int maxlength = 0;
        int start = 0;
        for (int i = 0; i < s.length(); i++) {
            if (map.size() >= 2 && !map.containsKey(s.charAt(i))) {
                int left = s.length();
                maxlength = Math.max(maxlength, i - start);
                for (Integer c : map.values()) {
                    if (c < left) {
                        left = c;
                    }
                }
                start = left + 1;
                map.remove(s.charAt(left));
                
            }
            map.put(s.charAt(i), i);
        }
        if (s.length() - start > maxlength) {
            maxlength = s.length() - start;
        }
        return maxlength;
    }
}