日期: 2025 年 3 月 13 日

目标

给你一个字符串 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;
    }
}

性能