[LeetCode] 每日一题 3305. 元音辅音字符串计数 I

题目链接

https://leetcode.cn/problems/count-of-substrings-containing-every-vowel-and-k-consonants-i

题目描述

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

解题思路

本题是典型的滑动窗口问题，要求计算子字符串中所有元音字母至少出现一次，并且恰好包含 k 个辅音字母的子串数量。一个巧妙的思路是利用「满足至少 k 个辅音字母的子串数量」减去「满足至少 k+1 个辅音字母的子串数量」，这样就能快速计算出恰好包含 k 个辅音字母的情况

具体实现中，定义一个 count 方法，统计至少包含 k 个辅音字母的子串数量。该方法使用滑动窗口，维护当前窗口内的辅音字母个数和元音字母的种类数，并且借助 Map 记录元音字母出现的次数。当窗口内的辅音字母不足 k 或者 5 种元音字母未全部出现时，不断扩展窗口 right；当条件满足时，计算满足条件的子串数量，并继续滑动窗口向右推进，保证窗口的动态调整

最终答案等于 count(k) - count(k + 1)，即满足至少 k 个辅音字母的子串数减去至少 k+1 个辅音字母的子串数，从而得到恰好包含 k 个辅音字母的情况

代码实现

class Solution {
    Set<Character> vowels = Set.of('a', 'e', 'i', 'o', 'u');

    public int countOfSubstrings(String word, int k) {
        char[] str = word.toCharArray();
        return count(str, k) - count(str, k + 1);
    }

    private int count(char[] str, int k) {
        int n = str.length;
        int consonantCount = 0;
        int vowelCount = 0;
        int res = 0;
        Map<Character, Integer> vowelMap = new HashMap<>(16);
        int right = 0;
        for (char c : str) {
            while (right < n && (consonantCount < k || vowelCount < 5)) {
                if (vowels.contains(str[right])) {
                    vowelMap.put(str[right], vowelMap.getOrDefault(str[right], 0) + 1);
                    if (vowelMap.get(str[right]) == 1) {
                        vowelCount++;
                    }
                } else {
                    consonantCount++;
                }
                right++;
            }
            if (consonantCount >= k && vowelCount == 5) {
                res += n - right + 1;
            }
            if (vowels.contains(c)) {
                vowelMap.put(c, vowelMap.get(c) - 1);
                if (vowelMap.get(c) == 0) {
                    vowelCount--;
                }
            } else {
                consonantCount--;
            }
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：整个代码的核心是滑动窗口，每个元素最多被访问两次（一次扩展窗口，一次收缩窗口），因此时间复杂度为 O(n)

• 空间复杂度：使用了一个 Map 记录元音字母出现次数，最多只包含 5 种元音字母，因此额外的空间复杂度为 O(1)，总体空间复杂度为 O(1)

总结

这道题利用了滑动窗口的技巧，在窗口扩展时保证满足条件的最短长度，并在窗口滑动过程中计算满足条件的子串数量。核心优化点是通过 count(k) - count(k+1) 方式计算恰好 k 个辅音字母的子串数量，从而降低时间复杂度到 O(n)

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。