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

摘要： 给定一个字符串 `word` 和一个非负整数 `k`，要求找出 `word` 中子字符串，每个元音字母（'a'、'e'、'i'、'o'、'u'）至少出现一次，并且恰好包含 `k` 个辅音字母的子字符串的总数。采用滑动窗口和哈希表的技巧来解决问题，通过遍历字符串并调整两个滑动窗口的左边界来满足条件。时间复杂度为 O(n)，空间复杂度为 O(1)。
  • 本文作者
  • 文章发布日期 2025-03-12 15:44
  • 热度 35
  • 作者心情 非常愉快
  • 本文共计
  • 预计阅读

题目要求

给你一个字符串 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 * 105

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

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

参考答案

参考答案代码

class Solution:
    def countOfSubstrings(self, word: str, k: int) -> int:
        cnt_vowel1 = defaultdict(int)
        cnt_vowel2 = defaultdict(int)
        cnt_consonant1 = cnt_consonant2 = 0
        ans = left1 = left2 = 0
        for b in word:
            if b in "aeiou":
                cnt_vowel1[b] += 1
                cnt_vowel2[b] += 1
            else:
                cnt_consonant1 += 1
                cnt_consonant2 += 1

            while len(cnt_vowel1) == 5 and cnt_consonant1 >= k:
                out = word[left1]
                if out in "aeiou":
                    cnt_vowel1[out] -= 1
                    if cnt_vowel1[out] == 0:
                        del cnt_vowel1[out]
                else:
                    cnt_consonant1 -= 1
                left1 += 1

            while len(cnt_vowel2) == 5 and cnt_consonant2 > k:
                out = word[left2]
                if out in "aeiou":
                    cnt_vowel2[out] -= 1
                    if cnt_vowel2[out] == 0:
                        del cnt_vowel2[out]
                else:
                    cnt_consonant2 -= 1
                left2 += 1

            ans += left1 - left2
        return ans

参考答案代码解析

初始化变量

cnt_vowel1 = defaultdict(int)
cnt_vowel2 = defaultdict(int)
cnt_consonant1 = cnt_consonant2 = 0
ans = left1 = left2 = 0

  • cnt_vowel1 和 cnt_vowel2：这两个 defaultdict 用于分别记录两个滑动窗口中每个元音字母的出现次数。defaultdict(int) 会在访问不存在的键时自动返回默认值 0。

  • cnt_consonant1 和 cnt_consonant2：分别记录两个滑动窗口中辅音字母的数量。

  • ans：用于存储满足条件的子字符串的数量。

  • left1 和 left2：分别是两个滑动窗口的左边界。

遍历字符串

for b in word:
    if b in "aeiou":
        cnt_vowel1[b] += 1
        cnt_vowel2[b] += 1
    else:
        cnt_consonant1 += 1
        cnt_consonant2 += 1

  • 遍历字符串 word 中的每个字符 b。

  • 如果 b 是元音字母（即 b 在 "aeiou" 中），则将 cnt_vowel1 和 cnt_vowel2 中对应元音字母的计数加 1。

  • 如果 b 是辅音字母，则将 cnt_consonant1 和 cnt_consonant2 的计数加 1。

调整第一个滑动窗口

while len(cnt_vowel1) == 5 and cnt_consonant1 >= k:
    out = word[left1]
    if out in "aeiou":
        cnt_vowel1[out] -= 1
        if cnt_vowel1[out] == 0:
            del cnt_vowel1[out]
    else:
        cnt_consonant1 -= 1
    left1 += 1

  • 当第一个滑动窗口中包含所有五个元音字母（即 len(cnt_vowel1) == 5），并且辅音字母的数量大于等于 k 时，需要调整窗口的左边界。

  • 取出左边界的字符 out，如果 out 是元音字母，则将其在 cnt_vowel1 中的计数减 1。如果计数变为 0，则从 cnt_vowel1 中删除该键。

  • 如果 out 是辅音字母，则将 cnt_consonant1 的计数减 1。

  • 将左边界 left1 右移一位。

调整第二个滑动窗口

while len(cnt_vowel2) == 5 and cnt_consonant2 > k:
    out = word[left2]
    if out in "aeiou":
        cnt_vowel2[out] -= 1
        if cnt_vowel2[out] == 0:
            del cnt_vowel2[out]
    else:
        cnt_consonant2 -= 1
    left2 += 1

  • 当第二个滑动窗口中包含所有五个元音字母（即 len(cnt_vowel2) == 5），并且辅音字母的数量大于 k 时，需要调整窗口的左边界。

  • 取出左边界的字符 out，如果 out 是元音字母，则将其在 cnt_vowel2 中的计数减 1。如果计数变为 0，则从 cnt_vowel2 中删除该键。

  • 如果 out 是辅音字母，则将 cnt_consonant2 的计数减 1。

  • 将左边界 left2 右移一位。

计算满足条件的子字符串数量

ans += left1 - left2

  • 每次遍历后，将 left1 - left2 的值累加到 ans 中。left1 - left2 表示以当前右边界结尾，满足包含所有五个元音字母且辅音字母数量恰好为 k 的子字符串的数量。

返回结果

return ans

  • 最后返回满足条件的子字符串的总数。

第二个窗口（left2）调整条件为 “大于 k” 的原因

  • 排除多余辅音情况：当第二个滑动窗口中包含所有五个元音字母且辅音字母数量大于 k 时，说明当前窗口中的辅音字母数量过多，不符合 “辅音字母数量恰好为 k” 的条件。此时需要不断缩小窗口，即右移左边界 left2，直到窗口内辅音字母数量不大于 k。这样做是为了排除那些辅音字母数量超过 k 的子字符串，确保窗口内的情况是接近满足条件的。

  • 计算可行子串数量：结合第一个窗口（left1）的条件（包含所有五个元音字母且辅音字母数量大于等于 k），left1 确定了满足 “包含所有元音且辅音数量至少为 k” 的最大范围，left2 确定了满足 “包含所有元音且辅音数量大于 k” 的最大范围。那么两者之间的差值 left1 - left2 就表示了以当前遍历位置为右边界时，辅音字母数量恰好为 k 的子字符串数量。

复杂度分析

  • 时间复杂度：(O(n))，其中 n 是字符串 word 的长度。因为只对字符串进行了一次遍历，并且每个字符最多被访问两次（一次是添加到窗口，一次是从窗口移除）。

  • 空间复杂度：(O(1))，因为 cnt_vowel1 和 cnt_vowel2 最多只存储五个元音字母的计数，所以空间复杂度是常数级的。