[LeetCode] 每日一题 3305. 元音辅音字符串计数 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)
希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。