Longest Substring with At Most Two Distinct Characters

Source

• leetcode: 159

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.

题解

我们遍历字符串时用一个哈希表，但这个哈希表只记录两个东西，一个字母和它上次出现的时的下标，另一个字母和它上次出现时候的下标。这样，如果新来的字母已经存在与表中，或者表中现在少于两个字母，就没关系，我们只要更新下它新的下标就行了。如果不存在于表中，则找出表中两个字母中，靠前面的那个，然后把这个较前的字母去掉，再加入这个新的字母。这样，我们就能维护一个窗口，保证其中只有两种字母。每次加入新字母时，说明上一个子串已经达到最长了，这时候我们判断下时候要更新全局最长子串就行了。这个通过用哈希表记录字母上次出现的下标，来维护一个窗口的方法也可以用于Longest Substring Without Repeating Characters。

Java

public class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        if(s.length() < 1) return 0;
        HashMap<Character,Integer> index = new HashMap<Character,Integer>();
        int lo = 0;
        int hi = 0;
        int maxLength = 0;
        while(hi < s.length()) {
            if(index.size() <= 2) {
                char c = s.charAt(hi);
                index.put(c, hi);
                hi++;
            }
            if(index.size() > 2) {
                int leftMost = s.length();
                for(int i : index.values()) {
                    leftMost = Math.min(leftMost,i);
                }
                char c = s.charAt(leftMost);
                index.remove(c);
                lo = leftMost+1;
            }
            maxLength = Math.max(maxLength, hi-lo);
        }
        return maxLength;
    }
}