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

题目链接

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

题目描述

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

解题思路

本题与昨天的题目本质相同，唯一的区别是字符串的长度上限从 250 增加到了 200000，使得暴力解法不可行，但我们的滑动窗口方法仍然适用

核心思想依然是利用「至少 k 个辅音字母」的子串数量减去「至少 k+1 个辅音字母」的子串数量，转换为两个范围求差，最终得到恰好包含 k 个辅音字母的子串数量

具体实现中，使用 count(k) - count(k+1) 计算结果。count(k) 采用滑动窗口方法：

• 维护 consonantCount 记录当前窗口内的辅音字母数量

• 维护 vowelCount 记录窗口内不同元音字母的种类数（最多 5 种）

• 通过 Map 记录元音字母的出现次数，确保窗口内所有元音字母至少出现一次

• 右指针 right 进行扩展，使得窗口满足 consonantCount >= k 且 vowelCount == 5，然后计算满足条件的子串数量

• 左指针滑动时更新 Map 并动态调整窗口

这样，我们可以在 O(n) 的时间复杂度内解决问题，并适应更大的输入规模

代码实现

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

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

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

总结

本题的优化点与昨天一致，利用滑动窗口高效计算至少 k 个辅音字母的子串数量，并通过「至少 k 个」减去「至少 k+1 个」的方法，快速得到恰好 k 个辅音字母的子串数量
由于字符串长度增大，暴力解法不再适用，而滑动窗口依然保持 O(n) 复杂度，使得方法在大规模输入下依然高效

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