[LeetCode] 159. Longest Substring with At Most Two Distinct Characters

Given a string s, return the length of the longest substring that contains at most two distinct characters.

Example 1:
Input: s = “eceba”
Output: 3
Explanation: The substring is “ece” which its length is 3.

Example 2:
Input: s = “ccaabbb”
Output: 5
Explanation: The substring is “aabbb” which its length is 5.

Constraints:
1 <= s.length <= 105
s consists of English letters.

至多包含两个不同字符的最长子串。

题意是给一个字符串，请返回一个最长子串的长度，子串至多包含两个不同字符的最长子串。

思路 - 滑动窗口，类似76题

这题依然是用到 sliding window 的思想。给左右两个指针，并且创建一个 hashmap，key 是遍历到的字母，value 是字母最后一次出现位置的 index。扫描的时候，一开始只让右指针移动，把遍历到的字母和当前的坐标值加入hashmap。此时最大子串的长度就是左右指针的间距。当右指针遍历到第三个不同字母的时候，需要扫描hashmap，找到value（记为leftmost）最小的那个key并且删除这个键值对。此时左指针的位置是leftmost + 1。

复杂度

时间O(n)
空间O(1) - 虽然有 hashmap 但是 size 很小，只有 26 个字母

代码

Java实现

class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        // corner case
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        // normal case
        int start = 0;
        int end = 0;
        int res = Integer.MIN_VALUE;
        int counter = 0;
        int[] map = new int[256];
        while (end < s.length()) {
            char c1 = s.charAt(end);
            if (map[c1] == 0) {
                counter++;
            }
            map[c1]++;
            end++;
            while (counter > 2) {
                char c2 = s.charAt(start);
                map[c2]--;
                if (map[c2] == 0) {
                    counter--;
                }
                start++;
            }
            res = Math.max(res, end - start);
        }
        return res;
    }
}

JavaScript实现

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstringTwoDistinct = function (s) {
    let map = new Map();
    let left = 0;
    let max = 0;
    for (let right = 0; right < s.length; right++) {
        map.set(s[right], right);
        if (map.size > 2) {
            let leftMostChar = null;
            let leftMostIndex = Infinity;
            for (let [char, index] of map) {
                if (index < leftMostIndex) {
                    leftMostChar = char;
                    leftMostIndex = index;
                }
            }
            map.delete(leftMostChar);
            left = leftMostIndex + 1;
        }
        max = Math.max(max, right - left + 1);
    }
    return max;
};