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