class Solution {
public:
long long countOfSubstrings(string word, int k) {
}
};
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 * 105word 仅由小写英文字母组成。0 <= k <= word.length - 5原站题解
java 解法, 执行用时: 51 ms, 内存消耗: 45.3 MB, 提交时间: 2024-10-09 22:04:29
class Solution {
public long countOfSubstrings(String word, int k) {
final int VOWEL_MASK = 1065233;
char[] s = word.toCharArray();
long 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;
}
}
cpp 解法, 执行用时: 146 ms, 内存消耗: 29.3 MB, 提交时间: 2024-10-09 22:03:55
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;
}
};
python3 解法, 执行用时: 1440 ms, 内存消耗: 17.5 MB, 提交时间: 2024-10-09 22:02:22
class Solution:
def f(self, word: str, k: int) -> int:
cnt1 = defaultdict(int) # 每种元音的个数
ans = cnt2 = left = 0 # cnt2 维护辅音个数
for b in word:
if b in "aeiou":
cnt1[b] += 1
else:
cnt2 += 1
while len(cnt1) == 5 and cnt2 >= k:
out = word[left]
if out in "aeiou":
cnt1[out] -= 1
if cnt1[out] == 0:
del cnt1[out]
else:
cnt2 -= 1
left += 1
ans += left
return ans
def countOfSubstrings(self, word: str, k: int) -> int:
return self.f(word, k) - self.f(word, k + 1)