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.

Analysis

Sliding window problem. Use a hash map to record all character and its most recent index. When we need to update the left pointer, iterate through hash map to find the character with the smallest index value, which is the current left pointer. Remove it from the hash map; The new left pointer index is the old one + 1.

My Solution

public int lengthOfLongestSubstringTwoDistinct(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    if (s.length() < 3) {
        return s.length();
    }
    Map<Character, Integer> map = new HashMap<>();
    int slow = 0;
    int len = 0;
    for (int f = 0; f < s.length(); ++f) {
        if (!map.containsKey(s.charAt(f))) {
            if (map.size() == 2) {
                Integer leftMost = Integer.MAX_VALUE;
                for (Map.Entry<Character, Integer> entry : map.entrySet()) {
                    if (entry.getValue() < leftMost) {
                        leftMost = entry.getValue();
                    }
                }
                map.remove(s.charAt(leftMost));
                slow = leftMost + 1;
            }
        }
        map.put(s.charAt(f), f);
        len = Math.max(len, f - slow + 1);
    }
    return len;
}

Solution 2

(use map.values() instead of Map.Entry)

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;
}