[LeetCode] 每日一题 3306. 元音辅音字符串计数 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) 复杂度,使得方法在大规模输入下依然高效
希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。