3306. 元音辅音字符串计数 II

Problem: 3306. 元音辅音字符串计数 II
周赛时没做出来，思路见灵茶山艾府

思路

这题初做没有做出来，因为没有理解双指针滑动窗口的特点：需要保证维护的子串满足一定的单调性，即长度变长，只可能更满足或者保持现状；变短反之。但是，如果任务是恰好型，并不能说越长越容易恰好，可能情况会变坏，所以是不能直接用双指针来做的。

但是，我们可以把问题进行转换，至少有五个元音字母的条件不变，恰好包含 k 个辅音字母的条件，可以转为以下两个至少型任务：

1. 每个元音字母至少出现一次，并且至少包含k个辅音字母的子串个数。
2. 每个元音字母至少出现一次，并且至少包含k+1个辅音字母的子串个数。

这样，只需要两个任务的答案相减，就可以求出恰好k个的答案。

Java解题技巧

HashMap使用

m.merge(key, 1, Integer::sum);
m.merge(key, -1, Integer::sum)

可以不用判空地进行Map的值增减操作。

另外，要判断是否为元音，可以使用

"aeiou".indexOf(out) >= 0

复杂度

• 时间复杂度: $O(n)$，双指针两次遍历一遍数组。
• 空间复杂度: $O(1)$。

Code

class Solution {
    public long countOfSubstrings(String word, int k) {
        char[] s = word.toCharArray();
        return f(s, k) - f(s, k + 1);
    }

    private long f(char[] word, int k) {
        long ans = 0;
        // 这里用哈希表实现，替换成数组会更快
        HashMap<Character, Integer> cnt1 = new HashMap<>(); // 每种元音的个数
        int cnt2 = 0; // 辅音个数
        int left = 0;
        for (char b : word) {
            if ("aeiou".indexOf(b) >= 0) {
                cnt1.merge(b, 1, Integer::sum); // ++cnt1[b]
            } else {
                cnt2++;
            }
            while (cnt1.size() == 5 && cnt2 >= k) {
                char out = word[left];
                if ("aeiou".indexOf(out) >= 0) {
                    if (cnt1.merge(out, -1, Integer::sum) == 0) { // --cnt1[out] == 0
                        cnt1.remove(out);
                    }
                } else {
                    cnt2--;
                }
                left++;
            }
            ans += left;
        }
        return ans;
    }
}