class Solution {
public:
int countOfSubstrings(string word, int k) {
}
};
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 <= 250word 仅由小写英文字母组成。0 <= k <= word.length - 5原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 4.1 MB, 提交时间: 2025-03-12 09:15:12
func countOfSubstrings(word string, k int) (ans int) {
const vowelMask = 1065233
var cntVowel1, cntVowel2 ['u' - 'a' + 1]int
sizeVowel1, sizeVowel2 := 0, 0 // 元音种类数
cntConsonant1, cntConsonant2 := 0, 0
left1, left2 := 0, 0
for _, b := range word {
b -= 'a'
if vowelMask>>b&1 > 0 {
if cntVowel1[b] == 0 {
sizeVowel1++
}
cntVowel1[b]++
if cntVowel2[b] == 0 {
sizeVowel2++
}
cntVowel2[b]++
} else {
cntConsonant1++
cntConsonant2++
}
for sizeVowel1 == 5 && cntConsonant1 >= k {
out := word[left1] - 'a'
if vowelMask>>out&1 > 0 {
cntVowel1[out]--
if cntVowel1[out] == 0 {
sizeVowel1--
}
} else {
cntConsonant1--
}
left1++
}
for sizeVowel2 == 5 && cntConsonant2 > k {
out := word[left2] - 'a'
if vowelMask>>out&1 > 0 {
cntVowel2[out]--
if cntVowel2[out] == 0 {
sizeVowel2--
}
} else {
cntConsonant2--
}
left2++
}
ans += left1 - left2
}
return
}
cpp 解法, 执行用时: 4 ms, 内存消耗: 9.5 MB, 提交时间: 2025-03-12 09:12:10
class Solution {
public:
long long countOfSubstrings(string word, int k) {
const int VOWEL_MASK = 1065233;
long long ans = 0;
int cnt_vowel1['u' - 'a' + 1]{}, cnt_vowel2['u' - 'a' + 1]{};
int size_vowel1 = 0, size_vowel2 = 0; // 元音种类数
int cnt_consonant1 = 0, cnt_consonant2 = 0;
int left1 = 0, left2 = 0;
for (int b : word) {
b -= 'a';
if (VOWEL_MASK >> b & 1) {
if (cnt_vowel1[b]++ == 0) {
size_vowel1++;
}
if (cnt_vowel2[b]++ == 0) {
size_vowel2++;
}
} else {
cnt_consonant1++;
cnt_consonant2++;
}
while (size_vowel1 == 5 && cnt_consonant1 >= k) {
char out = word[left1] - 'a';
if (VOWEL_MASK >> out & 1) {
if (--cnt_vowel1[out] == 0) {
size_vowel1--;
}
} else {
cnt_consonant1--;
}
left1++;
}
while (size_vowel2 == 5 && cnt_consonant2 > k) {
char out = word[left2] - 'a';
if (VOWEL_MASK >> out & 1) {
if (--cnt_vowel2[out] == 0) {
size_vowel2--;
}
} else {
cnt_consonant2--;
}
left2++;
}
ans += left1 - left2;
}
return ans;
}
};
java 解法, 执行用时: 1 ms, 内存消耗: 41.6 MB, 提交时间: 2024-10-09 22:05:34
class Solution {
public int countOfSubstrings(String word, int k) {
final int VOWEL_MASK = 1065233;
char[] s = word.toCharArray();
int ans = 0;
int[] cntVowel1 = new int['u' - 'a' + 1], cntVowel2 = new int['u' - 'a' + 1];
int sizeVowel1 = 0, sizeVowel2 = 0; // 元音种类数
int cntConsonant1 = 0, cntConsonant2 = 0;
int left1 = 0, left2 = 0;
for (char b : s) {
b -= 'a';
if ((VOWEL_MASK >> b & 1) > 0) {
if (cntVowel1[b]++ == 0) {
sizeVowel1++;
}
if (cntVowel2[b]++ == 0) {
sizeVowel2++;
}
} else {
cntConsonant1++;
cntConsonant2++;
}
while (sizeVowel1 == 5 && cntConsonant1 >= k) {
int out = s[left1] - 'a';
if ((VOWEL_MASK >> out & 1) > 0) {
if (--cntVowel1[out] == 0) {
sizeVowel1--;
}
} else {
cntConsonant1--;
}
left1++;
}
while (sizeVowel2 == 5 && cntConsonant2 > k) {
int out = s[left2] - 'a';
if ((VOWEL_MASK >> out & 1) > 0) {
if (--cntVowel2[out] == 0) {
sizeVowel2--;
}
} else {
cntConsonant2--;
}
left2++;
}
ans += left1 - left2;
}
return ans;
}
}
python3 解法, 执行用时: 47 ms, 内存消耗: 16.6 MB, 提交时间: 2024-10-09 22:02:42
class Solution:
def countOfSubstrings(self, word: str, k: int) -> int:
cnt_vowel1 = defaultdict(int)
cnt_vowel2 = defaultdict(int)
cnt_consonant1 = cnt_consonant2 = 0
ans = left1 = left2 = 0
for b in word:
if b in "aeiou":
cnt_vowel1[b] += 1
cnt_vowel2[b] += 1
else:
cnt_consonant1 += 1
cnt_consonant2 += 1
while len(cnt_vowel1) == 5 and cnt_consonant1 >= k:
out = word[left1]
if out in "aeiou":
cnt_vowel1[out] -= 1
if cnt_vowel1[out] == 0:
del cnt_vowel1[out]
else:
cnt_consonant1 -= 1
left1 += 1
while len(cnt_vowel2) == 5 and cnt_consonant2 > k:
out = word[left2]
if out in "aeiou":
cnt_vowel2[out] -= 1
if cnt_vowel2[out] == 0:
del cnt_vowel2[out]
else:
cnt_consonant2 -= 1
left2 += 1
ans += left1 - left2
return ans