[LeetCode] 3325. Count Substrings With K-Frequency Characters I

Given a string s and an integer k, return the total number of substrings of s where at least one character appears at least k times.

Example 1:
Input: s = “abacb”, k = 2
Output: 4

Explanation:
The valid substrings are:
“aba” (character ‘a’ appears 2 times).
“abac” (character ‘a’ appears 2 times).
“abacb” (character ‘a’ appears 2 times).
“bacb” (character ‘b’ appears 2 times).

Example 2:
Input: s = “abcde”, k = 1
Output: 15

Explanation:
All substrings are valid because every character appears at least once.

Constraints:
1 <= s.length <= 3000
1 <= k <= s.length
s consists only of lowercase English letters.

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

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

子字符串 是字符串中的一个连续、 非空 的字符序列。

思路

这道题类似 1358 题，也是滑动窗口里找一个越长越合法的子串。建议先做 1358 题，几乎是一样的。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public int numberOfSubstrings(String s, int k) {
        int[] map = new int[26];
        int n = s.length();
        int start = 0;
        int end = 0;
        int res = 0;
        while (end < n) {
            char c1 = s.charAt(end);
            map[c1 - 'a']++;
            end++;
			// 至少有一个字符出现 k 次吗？是，移动左指针
            while (helper(map, k) == true) {
                char c2 = s.charAt(start);
                map[c2 - 'a']--;
                start++;
            }
			// 跳出while循环前的所有[start, end]都是合法的子串
            res += start;
        }
        return res;
    }

    private boolean helper(int[] map, int k) {
        for (int i = 0; i < map.length; i++) {
            if (map[i] >= k) {
                return true;
            }
        }
        return false;
    }
}

相关题目

1358. Number of Substrings Containing All Three Characters
3325. Count Substrings With K-Frequency Characters I