日期: 2025 年 3 月 12 日

目标

给你一个字符串 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 <= 250
• word 仅由小写英文字母组成。
• 0 <= k <= word.length - 5

思路

求给定字符串 word 的子字符串中至少包含 5 个元音且恰好包含 k 个辅音的子字符串个数。

暴力枚举子数组。

代码

/**
 * @date 2025-03-12 8:42
 */
public class CountOfSubstrings3305 {

    public int countOfSubstrings(String word, int k) {
        int n = word.length();
        Set<Character> vowel = new HashSet<>();
        Collections.addAll(vowel, 'a', 'e', 'i', 'o', 'u');
        Map<Character, Integer> map = new HashMap<>();
        int consonantCnt = 0;
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                char c = word.charAt(j);
                if (vowel.contains(c)) {
                    Integer cnt = map.getOrDefault(c, 0);
                    map.put(c, cnt + 1);
                } else {
                    consonantCnt++;
                }
                if (consonantCnt == k && map.size() == 5) {
                    res++;
                } else if (consonantCnt > k) {
                    break;
                }
            }
            map.clear();
            consonantCnt = 0;
        }
        return res;
    }

}

性能