Leetcode-每日一题3306.-元音辅音字符串计数-II
目录
【Leetcode 每日一题】3306. 元音辅音字符串计数 II
问题背景
给你一个字符串
w o r d word
w
or
d 和一个 非负 整数
k k
k 。
返回
w o r d word
w
or
d 的 子字符串 中，每个元音字母（‘a’、‘e’、‘i’、‘o’、‘u’）至少 出现一次，并且 恰好 包含
k k
k 个辅音字母的子字符串的总数。
数据约束
5 ≤ w o r d . l e n g t h ≤ 2 × 1 0 5 5 \le word.length \le 2 \times 10 ^ 5
5
≤
w
or
d
.
l
e
n
g
t
h
≤
2
×
1
0
5
w o r d word
w
or
d 仅由小写英文字母组成。
0 ≤ k ≤ w o r d . l e n g t h − 5 0 \le k \le word.length - 5
0
≤
k
≤
w
or
d
.
l
e
n
g
t
h
−
5
解题过程
和 题干完全一样，只有数据范围的区别，用滑窗同样能解决。
具体实现
class Solution {
private String VOWEL = "aeiou";
public int countOfSubstrings(String word, int k) {
char[] chW = word.toCharArray();
return cal(chW, k) - cal(chW, k + 1);
}
private int cal(char[] chW, int k) {
int res = 0;
Map<Character, Integer> map = new HashMap<>();
int count = 0;
for (int left = 0, right = 0; right < chW.length; right++) {
char inChar = chW[right];
if (VOWEL.indexOf(inChar) >= 0) {
map.merge(inChar, 1, Integer::sum);
} else {
count++;
}
while (map.size() == 5 && count >= k) {
char outChar = chW[left];
if (VOWEL.indexOf(outChar) >= 0) {
if (map.merge(outChar, -1, Integer::sum) == 0) {
map.remove(outChar);
}
} else {
count--;
}
left++;
}
res += left;
}
return res;
}
}