文章

[LeetCode] 每日一题 3306. 元音辅音字符串计数 II

题目链接

https://leetcode.cn/problems/count-of-substrings-containing-every-vowel-and-k-consonants-ii

题目描述

给你一个字符串 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 <= 2 * 10^5

  • word 仅由小写英文字母组成。

  • 0 <= k <= word.length - 5

解题思路

本题与昨天的题目本质相同,唯一的区别是字符串的长度上限从 250 增加到了 200000,使得暴力解法不可行,但我们的滑动窗口方法仍然适用

核心思想依然是利用「至少 k 个辅音字母」的子串数量减去「至少 k+1 个辅音字母」的子串数量,转换为两个范围求差,最终得到恰好包含 k 个辅音字母的子串数量

具体实现中,使用 count(k) - count(k+1) 计算结果。count(k) 采用滑动窗口方法:

  • 维护 consonantCount 记录当前窗口内的辅音字母数量

  • 维护 vowelCount 记录窗口内不同元音字母的种类数(最多 5 种)

  • 通过 Map 记录元音字母的出现次数,确保窗口内所有元音字母至少出现一次

  • 右指针 right 进行扩展,使得窗口满足 consonantCount >= kvowelCount == 5,然后计算满足条件的子串数量

  • 左指针滑动时更新 Map 并动态调整窗口

这样,我们可以在 O(n) 的时间复杂度内解决问题,并适应更大的输入规模

代码实现

class Solution {
    Set<Character> vowels = Set.of('a', 'e', 'i', 'o', 'u');

    public long countOfSubstrings(String word, int k) {
        char[] wordCharArray = word.toCharArray();
        return count(wordCharArray, k) - count(wordCharArray, k + 1);
    }

    private long count(char[] word, int k) {
        int n = word.length;
        int consonantCount = 0;
        int vowelCount = 0;
        long res = 0;
        Map<Character, Integer> vowelMap = new HashMap<>(16);
        int right = 0;
        for (char c : word) {
            while (right < n && (consonantCount < k || vowelCount < 5)) {
                if (vowels.contains(word[right])) {
                    vowelMap.put(word[right], vowelMap.getOrDefault(word[right], 0) + 1);
                    if (vowelMap.get(word[right]) == 1) {
                        vowelCount++;
                    }
                } else {
                    consonantCount++;
                }
                right++;
            }
            if (consonantCount >= k && vowelCount == 5) {
                res += n - right + 1;
            }
            if (vowels.contains(c)) {
                vowelMap.put(c, vowelMap.get(c) - 1);
                if (vowelMap.get(c) == 0) {
                    vowelCount--;
                }
            } else {
                consonantCount--;
            }
        }
        return res;
    }
}

复杂度分析

  • 时间复杂度:滑动窗口保证每个字符最多被访问两次(一次进入窗口,一次离开窗口),因此时间复杂度为 O(n),适用于大规模数据

  • 空间复杂度Map 仅存储最多 5 个元音字母的计数,因此额外空间复杂度为 O(1),总体也是 O(1)

总结

本题的优化点与昨天一致,利用滑动窗口高效计算至少 k 个辅音字母的子串数量,并通过「至少 k 个」减去「至少 k+1 个」的方法,快速得到恰好 k 个辅音字母的子串数量
由于字符串长度增大,暴力解法不再适用,而滑动窗口依然保持 O(n) 复杂度,使得方法在大规模输入下依然高效

希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。

License:  CC BY 4.0