Longest Substring with At Most Two Distinct Characters

Problem: Longest Substring with At Most Two Distinct Characters

We use two pointers, one point to the head of sub-string, the other scan through the string to get longer sub-string. If we get to a new letter, we check whether it's in the current sub-string. If so, we can update our maximum length. If not, we can see whether there's only one character in current sub-string. If so, we make our new one as the second distinct characters and update maximum length. If not, we need to make a new sub-string by adjusting head pointer.

While adjusting head pointer, we can make the pointer going left from scanning pointer to get second distinct character as we treat the new letter as the first distinct letter. So that we can achieve longer sub-string.

Code in Python:

class Solution(object):
    def lengthOfLongestSubstringTwoDistinct(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s) == 1: return 1
        ans = 0
        i, distinct = 0, 1
        for j in xrange(1, len(s)):
            if distinct < 2 or s[j] in s[i:j]:
                if j-i+1 > ans: ans = j-i+1 
                if s[j] not in s[i:j]: distinct += 1
            else:
                i = j - 1
                while s[i-1] == s[i]:
                    i -= 1
        return ans

Code in Java:

public class Solution {
    public int lengthOfLongestSubstring(String s) {

        int len = s.length();
        if (len == 0) return 0;

        int l = 0, r = 1, res = 1;
        HashMap<Character, Integer> alphabet = new HashMap<Character, Integer>();
        alphabet.put(s.charAt(0), 1);

        while (r < len) {
            if (alphabet.get(s.charAt(r)) == null) {
                alphabet.put(s.charAt(r), 1);
                ++r;
                res = Math.max(res, r-l);
            } else {
                while (s.charAt(l) != s.charAt(r) && l <= r) {
                    alphabet.remove(s.charAt(l));
                    ++l;
                }
                ++l; ++r;
            }
        }

        return res;
    }
}