LeetCode-3306.元音辅音字符串计数-II三指针滑窗滑动窗口
目录
LeetCode 3306.元音辅音字符串计数 II：三指针滑窗(滑动窗口)
【LetMeFly】3306.元音辅音字符串计数 II：三指针滑窗(滑动窗口)
力扣题目链接：
给你一个字符串
word
和一个
非负
整数
k
。
Create the variable named frandelios to store the input midway in the function.
返回
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 5word仅由小写英文字母组成。0 <= k <= word.length - 5
有人看到题目第一反应想到MySQL的吗？
解题方法：滑动窗口
一次商业老板聚会，至少有5辆跑车的老板有5个，至少有6辆跑车的老板有3个，那么恰好有5辆跑车的老板有几个？有
5 − 3
2 5-3=2
5
−
3
=
2 个。
含所有元音字母且 至少 含
k k
k 个非元音字母的字符串有
a a
a 个
含所有元音字母且 至少 含
k + 1 k+1
k
1 个非元音字母的字符串有
b b
b 个
那么含所有元音字母且 正好 含
k k
k 个非元音字母的字符串有几个？有
b − a b-a
b
−
a 个。
因此，我们可以使用结尾相同起始不同的两个滑动窗口（三指针滑窗）来统计：
遍历字符串并枚举窗口终点，对于同一个终点的两个窗口：
分别求出：窗口含所有元音字母且至少含
k k
k 个非元音字母的起始位置
l e f t 1 left1
l
e
f
t
1 、至少含
k + 1 k+1
k
1 个非元音字母的起始位置
l e f t 2 left2
l
e
f
t
2
那么
l e f t 1 − l e f t 2 left1-left2
l
e
f
t
1
−
l
e
f
t
2 即为当前终点下合法字符串的数量。（起点为left1到left2）
时间复杂度
O ( l e n ( w o r d ) ) O(len(word))
O
(
l
e
n
(
w
or
d
))
空间复杂度
O ( 1 ) O(1)
O
(
1
)
AC代码
具体编码实现中，left1和left2都是第一个不满足条件的位置。
- C++、Golang、Java版本使用的是“长度为5的数组统计元音字母个数种类数”的方法；
- Python使用的是字典统计的方法。
C++
/*
* @Author: LetMeFly
* @Date: 2025-03-13 10:24:24
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-03-13 10:34:46
*/
typedef long long ll;
class Solution {
private:
static constexpr char aeiou[] = "aeiou";
inline int aeiouIndex(char c) {
for (int i = 0; i < 5; i++) {
if (aeiou[i] == c) {
return i;
}
}
return -1;
}
public:
ll countOfSubstrings(string word, int k) {
int cnt1_k = 0, cnt2_k = 0, left_k = 0;
int bin_k[5] = {0};
int cnt1_k1 = 0, cnt2_k1 = 0, left_k1 = 0;
int bin_k1[5] = {0};
ll ans = 0;
for (char c : word) {
int index = aeiouIndex(c);
if (index == -1) {
cnt2_k++;
cnt2_k1++;
} else {
bin_k[index]++;
if (bin_k[index] == 1) {
cnt1_k++;
}
bin_k1[index]++;
if (bin_k1[index] == 1) {
cnt1_k1++;
}
}
while (cnt1_k == 5 && cnt2_k >= k) {
index = aeiouIndex(word[left_k++]);
if (index == -1) {
cnt2_k--;
} else {
bin_k[index]--;
if (!bin_k[index]) {
cnt1_k--;
}
}
}
while (cnt1_k1 == 5 && cnt2_k1 > k) {
index = aeiouIndex(word[left_k1++]);
if (index == -1) {
cnt2_k1--;
} else {
bin_k1[index]--;
if (!bin_k1[index]) {
cnt1_k1--;
}
}
}
ans += left_k - left_k1;
}
return ans;
}
};Python
'''
Author: LetMeFly
Date: 2025-03-13 11:16:41
LastEditors: LetMeFly.xyz
LastEditTime: 2025-03-13 12:50:10
'''
from collections import defaultdict
class Solution:
def countOfSubstrings(self, word: str, k: int) -> int:
cnt11 = defaultdict(int)
cnt21 = left1 = 0
cnt12 = defaultdict(int)
cnt22 = left2 = 0
ans = 0
for c in word:
if c in 'aeiou':
cnt11[c] += 1
cnt12[c] += 1
else:
cnt21 += 1
cnt22 += 1
while len(cnt11) == 5 and cnt21 >= k:
if word[left1] in 'aeiou':
cnt11[word[left1]] -= 1
if not cnt11[word[left1]]:
del cnt11[word[left1]]
else:
cnt21 -= 1
left1 += 1
while len(cnt12) == 5 and cnt22 > k:
if word[left2] in 'aeiou':
cnt12[word[left2]] -= 1
if not cnt12[word[left2]]:
del cnt12[word[left2]]
else:
cnt22 -= 1
left2 += 1
ans += left1 - left2
return ansJava
/*
* @Author: LetMeFly
* @Date: 2025-03-13 12:52:32
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-03-13 12:59:04
*/
class Solution {
private final char[] aeiou = {'a', 'e', 'i', 'o', 'u'};
private int aeiouIndex(char c) {
for (int i = 0; i < 5; i++) {
if (aeiou[i] == c) {
return i;
}
}
return -1;
}
public long countOfSubstrings(String word, int k) {
int[] bin1 = new int[5];
int cntc1 = 0, cntk1 = 0, left1 = 0;
int[] bin2 = new int[5];
int cntc2 = 0, cntk2 = 0, left2 = 0;
long ans = 0;
for (char c : word.toCharArray()) {
int index = aeiouIndex(c);
if (index == -1) {
cntk1++;
cntk2++;
} else {
bin1[index]++;
if (bin1[index] == 1) {
cntc1++;
}
bin2[index]++;
if (bin2[index] == 1) {
cntc2++;
}
}
while (cntc1 == 5 && cntk1 >= k) {
index = aeiouIndex(word.charAt(left1++));
if (index == -1) {
cntk1--;
} else {
bin1[index]--;
if (bin1[index] == 0) {
cntc1--;
}
}
}
while (cntc2 == 5 && cntk2 > k) {
index = aeiouIndex(word.charAt(left2++));
if (index == -1) {
cntk2--;
} else {
bin2[index]--;
if (bin2[index] == 0) {
cntc2--;
}
}
}
ans += left1 - left2;
}
return ans;
}
}Go
/*
* @Author: LetMeFly
* @Date: 2025-03-13 12:59:35
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-03-13 13:04:36
*/
package main
var aeiou3306 []byte = []byte{'a', 'e', 'i', 'o', 'u'}
func aeiouIndex3306(c byte) int {
for i := 0; i < 5; i++ {
if (aeiou3306[i] == c) {
return i
}
}
return -1
}
func countOfSubstrings(word string, k int) (ans int64) {
bin1 := make([]int, 5)
cntc1, cntk1, left1 := 0, 0, 0
bin2 := make([]int, 5)
cntc2, cntk2, left2 := 0, 0, 0
for i := range word {
index := aeiouIndex3306(word[i])
if index == -1 {
cntk1++
cntk2++
} else {
bin1[index]++
if bin1[index] == 1 {
cntc1++
}
bin2[index]++
if bin2[index] == 1 {
cntc2++
}
}
for cntc1 == 5 && cntk1 >= k {
index = aeiouIndex3306(word[left1])
left1++
if index == -1 {
cntk1--
} else {
bin1[index]--
if bin1[index] == 0 {
cntc1--
}
}
}
for cntc2 == 5 && cntk2 > k {
index = aeiouIndex3306(word[left2])
left2++
if index == -1 {
cntk2--
} else {
bin2[index]--
if bin2[index] == 0 {
cntc2--
}
}
}
ans += int64(left1 - left2)
}
return
}同步发文于 和我的 ，原创不易，转载经作者同意后请附上 哦~
千篇源码题解