159. Longest Substring with At Most Two Distinct Characters

三刷 07/2022

Version #2 Array as map + Sliding Window

一开始写了一个bug，就是当character count数大于2的时候，完全remove 左边界start的所有character

这种遇到反例abaccc的时候，不需要完全消除a就可以消除b了

所以start要一步一步往前走

这个做法是记录了the index of the last occurrence of the character，如果记录count of the character也是一样的

Time O(N)

Space O(256) ~ O(1)

Runtime: 15 ms, faster than 91.66% of Java online submissions for Longest Substring with At Most Two Distinct Characters.

Memory Usage: 47.3 MB, less than 81.26% of Java online submissions for Longest Substring with At Most Two Distinct Characters.

class Solution {

    public int lengthOfLongestSubstringTwoDistinct(String s) {

        // key is the ascii number of the character, value is the last index of that character

        int[] map = new int[126];

        int len = 0;

        Arrays.fill(map, -1);

        int count = 0; // number of distinct characters in the sliding window

        int start = 0;

        for (int end = 0; end < s.length(); end++) {

            char c = s.charAt(end);

            if (map[c] < start) { // this is a new character

                count++;

            }

            map[c] = end; // update the last occurance

            while (count > 2) {

                if (map[s.charAt(start)] == start) {

                    count--;

                }

                start++;

            }

            len = Math.max(len, end - start + 1);

        }

        return len;

    }

}

Version #1 HashMap + Sliding Window
Time O(n)

二刷
48.56 %
class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        // key->char, value->count of char
        Map<Character, Integer> map = new HashMap<>();
        // (left, right]
        int left = -1;
        int right = 0;
        int count = 2;
        int max = 0;
        for (right = 0; right < s.length(); right++) {
            char r = s.charAt(right);
            int rCount = map.getOrDefault(r, 0);
            if (rCount == 0) {
                count--;
            }
            map.put(r, rCount + 1);
            while (count < 0 && ++left < right) {
                char l = s.charAt(left);
                int lCount = map.getOrDefault(l, 0);
                lCount--;
                if (lCount <= 0) {
                    count++;
                }
                map.put(l, lCount);
            }
            max = Math.max(max, right - left);
        }
        return max;
    }
}

Version #2 lasOccurance
一刷
Time O(kN)
10.00 %
class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        // key->char, value->last occurance index
        Map<Character, Integer> map = new HashMap<>();
        // (left, right]
        int left = -1;
        int right = 0;
        int max = 0;
        for (right = 0; right < s.length(); right++) {
            map.put(s.charAt(right), right);
            if (map.size() > 2) {
                int index = Collections.min(map.values());
                map.remove(s.charAt(index));
                left = index;
            }
            max = Math.max(max, right - left);
        }
        return max;
    }
}