3329：字符至少出现 K 次的子字符串 II（★★）

Ian

2024-10-25 约 295 字预计阅读 1 分钟次阅读

力扣第 3329 题

题目

给你一个字符串 s 和一个整数 k，在 s 的所有子字符串中，请你统计并返回 至少有一个 字符 至少出现 k 次的子字符串总数。

示例 1：

输入： s = "abacb", k = 2

输出： 4

解释：

符合条件的子字符串如下：

"aba"（字符 'a' 出现 2 次）。
"abac"（字符 'a' 出现 2 次）。
"abacb"（字符 'a' 出现 2 次）。
"bacb"（字符 'b' 出现 2 次）。

示例 2：

输入： s = "abcde", k = 1

输出： 15

解释：

所有子字符串都有效，因为每个字符至少出现一次。

提示：

1 <= s.length <= 3 * 10⁵
1 <= k <= s.length
s 仅由小写英文字母组成。

分析

滑动窗口，维护最短的符合的窗口即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution:
    def numberOfSubstrings(self, s: str, k: int) -> int:
        d = defaultdict(list)
        res = 0
        i = 0
        for j,c in enumerate(s):
            d[c].append(j)
            if len(d[c])>=k:
                i = max(i,d[c][-k]+1)
            res += i
        return res

576 ms

目录

3329：字符至少出现 K 次的子字符串 II（★★）

题目

分析

解答