跳转至

340. 至多包含 K 个不同字符的最长子串 🔒

题目描述

给你一个字符串 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;
}

评论