题目描述
给你一个字符串 s
和一个整数 k
,请你找出 至多 包含 k
个 不同 字符的最长子串,并返回该子串的长度。
示例 1:
输入:s = "eceba", k = 2
输出:3
解释:满足题目要求的子串是 "ece" ,长度为 3 。
示例 2:
输入:s = "aa", k = 1
输出:2
解释:满足题目要求的子串是 "aa" ,长度为 2 。
提示:
1 <= s.length <= 5 * 104
0 <= k <= 50
解法
方法一:滑动窗口 + 哈希表
我们可以使用滑动窗口的思想,用一个哈希表 $\textit{cnt}$ 记录窗口中每个字符的出现次数,用 $\textit{l}$ 记录窗口的左边界。
遍历字符串,每次将右边界的字符加入哈希表,如果哈希表中不同字符的个数超过了 $k$,则将左边界的字符从哈希表中删除,然后更新左边界 $\textit{l}$。
最后返回字符串的长度减去左边界的长度即可。
时间复杂度 $O(n)$,空间复杂度 $O(k)$。其中 $n$ 为字符串的长度。
1
2
3
4
5
6
7
8
9
10
11
12 | class Solution:
def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
l = 0
cnt = Counter()
for c in s:
cnt[c] += 1
if len(cnt) > k:
cnt[s[l]] -= 1
if cnt[s[l]] == 0:
del cnt[s[l]]
l += 1
return len(s) - l
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | class Solution {
public int lengthOfLongestSubstringKDistinct(String s, int k) {
Map<Character, Integer> cnt = new HashMap<>();
int l = 0;
char[] cs = s.toCharArray();
for (char c : cs) {
cnt.merge(c, 1, Integer::sum);
if (cnt.size() > k) {
if (cnt.merge(cs[l], -1, Integer::sum) == 0) {
cnt.remove(cs[l]);
}
++l;
}
}
return cs.length - l;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | class Solution {
public:
int lengthOfLongestSubstringKDistinct(string s, int k) {
unordered_map<char, int> cnt;
int l = 0;
for (char& c : s) {
++cnt[c];
if (cnt.size() > k) {
if (--cnt[s[l]] == 0) {
cnt.erase(s[l]);
}
++l;
}
}
return s.size() - l;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | func lengthOfLongestSubstringKDistinct(s string, k int) int {
cnt := map[byte]int{}
l := 0
for _, c := range s {
cnt[byte(c)]++
if len(cnt) > k {
cnt[s[l]]--
if cnt[s[l]] == 0 {
delete(cnt, s[l])
}
l++
}
}
return len(s) - l
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | function lengthOfLongestSubstringKDistinct(s: string, k: number): number {
const cnt: Map<string, number> = new Map();
let l = 0;
for (const c of s) {
cnt.set(c, (cnt.get(c) ?? 0) + 1);
if (cnt.size > k) {
cnt.set(s[l], cnt.get(s[l])! - 1);
if (cnt.get(s[l]) === 0) {
cnt.delete(s[l]);
}
l++;
}
}
return s.length - l;
}
|