【Leetcode 每日一题】3306. 元音辅音字符串计数 I

问题背景

给你一个字符串 $word$ 和一个 非负 整数 $k$。
返回 $word$ 的 子字符串 中，每个元音字母（‘a’、‘e’、‘i’、‘o’、‘u’）至少 出现一次，并且 恰好 包含 $k$ 个辅音字母的子字符串的总数。

数据约束

• $5\le word.length\le 250$
• $word$ 仅由小写英文字母组成。
• $0\le k\le word.length-5$

解题过程

出现次数相关的问题，首先想到要用哈希表来统计频次。
进一步来看，这题如果将所求问题转化为 至少包含 $k$ 个辅音字母，会方便很多，那么恰好可以表示为至少 $k$ 个和至少 $(k+1)$ 个之差。

具体实现

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;}
}