文章

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

题目链接

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

题目描述

给你一个字符串 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 <= 250

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

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

解题思路

本题是典型的滑动窗口问题,要求计算子字符串中所有元音字母至少出现一次,并且恰好包含 k 个辅音字母的子串数量。一个巧妙的思路是利用「满足至少 k 个辅音字母的子串数量」减去「满足至少 k+1 个辅音字母的子串数量」,这样就能快速计算出恰好包含 k 个辅音字母的情况

具体实现中,定义一个 count 方法,统计至少包含 k 个辅音字母的子串数量。该方法使用滑动窗口,维护当前窗口内的辅音字母个数和元音字母的种类数,并且借助 Map 记录元音字母出现的次数。当窗口内的辅音字母不足 k 或者 5 种元音字母未全部出现时,不断扩展窗口 right;当条件满足时,计算满足条件的子串数量,并继续滑动窗口向右推进,保证窗口的动态调整

最终答案等于 count(k) - count(k + 1),即满足至少 k 个辅音字母的子串数减去至少 k+1 个辅音字母的子串数,从而得到恰好包含 k 个辅音字母的情况

代码实现

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

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

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

总结

这道题利用了滑动窗口的技巧,在窗口扩展时保证满足条件的最短长度,并在窗口滑动过程中计算满足条件的子串数量。核心优化点是通过 count(k) - count(k+1) 方式计算恰好 k 个辅音字母的子串数量,从而降低时间复杂度到 O(n)

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

License:  CC BY 4.0