BiruLyu
5/22/2017 - 5:58 PM

159. Longest Substring with At Most Two Distinct Characters(#1 Sliding Window).java

/*
using hashset store at most 2 unique characters, however it is not easy to extend to k characters
using hashmap to store the last occurrence of each character coped with finding left most the character with the left most index
*/

public class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        if (s == null || s.length() == 0) return 0;
        int start = 0;
        int end = 0;
        int res = 0;
        //char[] dict = new char[2];
        //HashSet<Character> dict = new HashSet<Character>();
        HashMap<Character, Integer> dict = new HashMap<Character, Integer>();
        while( end < s.length()){
            if (dict.size() <= 2){
                dict.put(s.charAt(end), end);
                end++;
            } 
            if (dict.size() > 2) {
                int leftMost = s.length();
                for(int i : dict.values()){
                    leftMost = Math.min(leftMost, i);
                }
                dict.remove(s.charAt(leftMost));
                start = leftMost + 1;
            }
            res = Math.max(res, end - start);
        }
        return res;
        
    }
}
class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        if (s == null || s.length() < 1) return 0;
        int count = 0, end = 0, start = 0, res = 0;
        int[] vector = new int[256];
        char[] str = s.toCharArray();
        while (end < str.length) {
            if (vector[str[end++]]++ == 0) count++;
            while (count > 2) {
                if (--vector[str[start++]] == 0) count--;
            }
            res = Math.max(res, end - start);
        }
        return res;
    }
}