Leetcode 340. 至多包含 K 个不同字符的最长子串（滑动窗口）

给你一个字符串 s 和一个整数 k ，请你找出 至多 包含 k 个 不同 字符的最长子串，并返回该子串的长度。

---

示例 1：

输入：s = "eceba", k = 2
输出：3
解释：满足题目要求的子串是 "ece" ，长度为 3 。
示例 2：

输入：s = "aa", k = 1
输出：2
解释：满足题目要求的子串是 "aa" ，长度为 2 。
1
2
3
4
5
6
7
8
9
10

---

【代码】：
滑动窗口思路。
注意时间复杂度的控制，如果无脑O（n^2）会超时。
我这里用hash优化到了O（n）

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */ 

//滑动窗口。如果满足right++，扩大窗口。否则左边增加减小窗口
var lengthOfLongestSubstringKDistinct = function(s, k) {
    let left = 0;
    let right = 0;
    let arr = s.split("");
    let max = 0;
    let hash = new Map();
    hash.set(arr[0], 1);
    while(right < arr.length){    
        if(hash.size <= k){
            max = Math.max(max, right - left + 1);
            right++;
            let val = hash.get(arr[right]);
            val == undefined ? hash.set(arr[right],1) : hash.set(arr[right],val+1); 
        }else{
            let val = hash.get(arr[left]) - 1;
            val == 0 ? hash.delete(arr[left]) : hash.set(arr[left], val);
            left++;
        }
    }
    return max;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28