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原站题解
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