Problem

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.

思路(暴力)

• a counter to record distinct number
• a hash table to record distinct character
• for the ith char, go through every character from the i-1th char to the beginning and use hash table to record
• time complexity: O(n ^ 2)
• space complexity: O(n)

思路(two pointer)

优化思路:

• we cannot sort the string
• possible time complexity: O(n)
• two pointer, end and start. first add [end] to hash table, and see if table size is larger than 2, if it is, start++, etc

•   public int lengthOfLongestSubstringTwoDistinct(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int end = 0;
        int start = 0;
        Map<Character, Integer> hash = new HashMap<>();
        int res = 0;
        while (end < s.length()) {
            char ch = s.charAt(end);
            hash.put(ch, hash.getOrDefault(ch, 0) + 1);
            end++;
            while (hash.size() > 2) {
                char c = s.charAt(start);
                hash.put(c, hash.get(c) - 1);
                if (hash.get(c) == 0) {
                    hash.remove(c);
                }
                start++;
            }
            res = Math.max(res, end - start);
        }
        return res;
    }