Longest Substring with At Most Two Distinct Characters

• https://leetcode.com/problems/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.

Naive Solution: try every possible substring

Time complexity: O(n^2)

public int lengthOfLongestSubstringTwoDistinct(String s) {
    int maxLength = 0;
    for (int i = 0; i < s.length(); i++) {
        Set<Character> set = new HashSet();
        int length = 0;
        // test each substring start from j = i
        for (int j = i; j < s.length(); j++) {
            length++;
            if (!set.contains(s.charAt(j))) {
                set.add(s.charAt(j));
                if (set.size() == 3) {
                    length--;
                    break;
                }
            }
        }
        maxLength = Math.max(maxLength, length);
    }

    return maxLength;
}

Time complexity: O(n * 2)

public int lengthOfLongestSubstringTwoDistinct(String s) {
    int maxLength = 0 ;
    Map<Character, Integer> map = new HashMap();
    int left = 0;

    for (int i = 0; i < s.length(); i++) {
        // when we meet the third unique character
        if (map.size() == 2 && !map.containsKey(s.charAt(i))) {
            int length = i - left;
            maxLength = Math.max(length, maxLength);

            int leftMostIndex = Integer.MAX_VALUE;
            // find the left most character
            for (Character c : map.keySet()) {
                if (map.get(c) < leftMostIndex) {
                    leftMostIndex = map.get(c);
                }
            }

            left = leftMostIndex + 1; // set the left index to be the one deleted plus one 
            // remove the left most index from the map
            map.remove(s.charAt(leftMostIndex));

        }
        map.put(s.charAt(i), i);
    }

    maxLength = Math.max(maxLength, s.length() -left); // handle the last case
    if (map.size() <= 2 && maxLength == 0) {
        return s.length();
    }
    return maxLength;
}