当前位置：首页 > article >正文

Leetcode 3325. Count Substrings With K-Frequency Characters I

article 2024/10/21 10:24:20

Leetcode 3325. Count Substrings With K-Frequency Characters I
- 1. 解题思路
- 2. 代码实现

题目链接：3325. Count Substrings With K-Frequency Characters I

1. 解题思路

这一题思路上就是一个滑动窗口。

我们考察窗口的左边界依次为0到n-1时右边界能够取到的最小值，使之满足至少有一个字符的频次不小于k，此时后续所有的子串都满足条件，显然窗口的有边界同样是单调递增的，因此我们用一个滑动窗口即可完成上述思路。

2. 代码实现

给出python代码实现如下：

class Solution:
    def numberOfSubstrings(self, s: str, k: int) -> int:
        n = len(s)
        cnt = [0 for _ in range(26)]
        i, j = 0, 0
        ans = 0
        while i < n:
            while j < n and max(cnt) < k:
                cnt[ord(s[j]) - ord('a')] += 1
                j += 1
            if max(cnt) >= k:
                ans += n-j+1
            else:
                break
            cnt[ord(s[i]) - ord('a')] -= 1
            i += 1
        return ans