3325. 字符至少出现 K 次的子字符串 I

题目描述

给你一个字符串 s 和一个整数 k，统计并返回所有至少有一个字符至少出现 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
- 解析：所有子字符串都满足条件，因为每个字符至少出现一次。

代码实现

这个K不在是一个范围的长，而是范围合法的要求

public class Solution {
    public int numberOfSubstrings(String s, int k) {
        int n = s.length();
        int result = 0;
        int[] count = new int[26]; 
        int l = 0;

        for (int r = 0; r < n; r++) {
            count[s.charAt(r) - 'a']++;
            while (check(count, k)) {
                result += n - r;
                count[s.charAt(l) - 'a']--;
                l++;
            }
        }

        return result;
    }

    private boolean check(int[] count, int k) {
        for (int c : count) {
            if (c >= k) {
                return true;
            }
        }
        return false;
    }
}

分析

思路：利用滑动窗口来维护一个窗口，使得窗口内至少有一个字符出现次数大于等于 k。
窗口调整：
- 当窗口右边界增加字符时，检查当前窗口是否满足条件。
- 如果满足，说明从 l 到 r 的所有子字符串都符合条件，累加结果。
- 然后缩小窗口的左边界，并继续检查。
时间复杂度：O(n)，双指针法遍历字符串。