Leetcode: 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.

Understand the problem:

The problem looks quite similar to a previous problem:

http://buttercola.blogspot.com/2014/08/leetcode-longest-substring-without.html

The idea is still to use two pointers, i and j. We move the pointer i forward and put the visited character as well as its times into a map. We also need to increase the counter if the character is not in the map. 

When the counter is greater than 2, we need to move the second pointer j and try to decrease the counter. However, we cannot just decrease the counter by 1 once we move the j pointer a step forward. e.g. b e c e a. When the i pointer is at a, and j pointer is at e, move the j pointer from e to c does not decrease the counter (still 3). Therefore, the condition to decrease the counter is when the character is not in the map again. 

Code (Java):

public class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        if (s == null || s.length() < 3) {
            return s.length();
        }
        
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        int maxLen = 0;
        int j = 0;
        int counter = 0;
        
        for (int i = 0; i < s.length(); i++) {
            char element = s.charAt(i);
            if (!map.containsKey(element)) {
                counter++;
                map.put(element, 1);
                
                while (j < i && counter > 2) {
                    if (map.get(s.charAt(j)) == 1) {
                        map.remove(s.charAt(j));
                    } else {
                        int tmp = map.get(s.charAt(j)) - 1;
                        map.put(s.charAt(j), tmp);
                    }
                    
                    if (!map.containsKey(s.charAt(j))) {
                        counter--;
                    }
                    j++;
                }
            } else {
                int tmp = map.get(s.charAt(i));
                map.put(s.charAt(i), tmp + 1);
            }
            
            maxLen = Math.max(maxLen, i - j + 1);
        }
        
        return maxLen;
        
    }
}

Analysis:
Time complexity is O(n) since we only move the pointers forward. The space complexity is at O(k) where k the number of distinct numbers in the substring. In this case, k is 2. 

Update on 10/13/15:

public class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        Map<Character, Integer> map = new HashMap<>();
        
        int j = 0;
        int i = 0;
        int len = 0;
        
        for (i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!map.containsKey(c)) {
                map.put(c, i);
            } else {
                int pos = map.get(c);
                map.put(c, i);
            }
            
            if (map.size() > 2) {
                len = Math.max(len, i - j);
                
                // Then shrink the window size
                while (map.size() > 2) {
                    if (map.containsKey(s.charAt(j)) && map.get(s.charAt(j)) == j) {
                        map.remove(s.charAt(j));
                    }
                    j++;
                }
            }
        }
        
        if (j < s.length()) {
            len = Math.max(len, i - j);
        }
        
        return len;
     }
}