目标
给你一个字符串 word 和一个 非负 整数 k。
返回 word 的 子字符串 中，每个元音字母（'a'、'e'、'i'、'o'、'u'）至少 出现一次，并且 恰好 包含 k 个辅音字母的子字符串的总数。
示例 1：
输入：word = "aeioqq", k = 1
输出：0
解释：
不存在包含所有元音字母的子字符串。示例 2：
输入：word = "aeiou", k = 0
输出：1
解释：
唯一一个包含所有元音字母且不含辅音字母的子字符串是 word[0..4]，即 "aeiou"。示例 3：
输入：word = "ieaouqqieaouqq", k = 1
输出：3
解释：
包含所有元音字母并且恰好含有一个辅音字母的子字符串有：
word[0..5]，即 "ieaouq"。
word[6..11]，即 "qieaou"。
word[7..12]，即 "ieaouq"。说明：
- 5 <= word.length <= 2 * 10^5
- word 仅由小写英文字母组成。
- 0 <= k <= word.length - 5
思路
求给定字符串 word 的子字符串中至少包含 5 个元音且恰好包含 k 个辅音的子字符串个数。
与 3305.元音辅音字符串计数I 相比，字符串长度范围变成了 2 * 10^5。
恰好型滑动窗口，区间 [left, right] 满足条件不代表 [left, right + 1] 满足条件，可能辅音数量超过了 k，这样就不能累加前面的起点数量，需要重新遍历起点排除一个辅音，退化成暴力解法。
题解提到 恰好 k 个辅音字母 = 至少 k 个辅音字母 - 至少 k + 1 个辅音字母，这样就可以使用两个滑动窗口来求解。
代码
/**
* @date 2025-03-13 17:03
*/
public class CountOfSubstrings3306 {
public long countOfSubstrings(String word, int k) {
return slidingWindow(word, k) - slidingWindow(word, k + 1);
}
public long slidingWindow(String word, int k) {
Set<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u'));
Map<Character, Integer> map = new HashMap<>();
int n = word.length();
int consonantCnt = 0;
long res = 0;
int left = 0;
for (int right = 0; right < n; right++) {
char c = word.charAt(right);
if (vowels.contains(c)) {
Integer cnt = map.getOrDefault(c, 0);
map.put(c, cnt + 1);
} else {
consonantCnt++;
}
while (left <= right && consonantCnt >= k && map.size() == 5) {
c = word.charAt(left++);
if (vowels.contains(c)) {
map.merge(c, -1, Integer::sum);
if (map.get(c) == 0) {
map.remove(c);
}
} else {
consonantCnt--;
}
}
res += left;
}
return res;
}
}
性能
