2025-05-03：元音辅音字符串计数Ⅰ。用go语言，给定一个字符串 word 和一个非负整数 k。我们需要找出 word 的

福大大架构师每日一题

发布于 2025-05-04 10:26:28

21200

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

2025-05-03：元音辅音字符串计数Ⅰ。用go语言，给定一个字符串 word 和一个非负整数 k。我们需要找出 word 的所有子字符串中，满足以下两个条件的子字符串的数量：

1.元音字母齐全：子字符串中必须包含所有的五个元音字母（即 'a'、'e'、'i'、'o'、'u'），每个至少出现一次。

2.辅音字母数量恰好：子字符串中辅音字母的数量必须恰好等于 k。

最终返回满足这两个条件的子字符串的总数。

5 <= word.length <= 250。

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

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

输入：word = "ieaouqqieaouqq", k = 1。

输出：3。

解释：

包含所有元音字母并且恰好含有一个辅音字母的子字符串有：

word[0..5]，即 "ieaouq"。

word[6..11]，即 "qieaou"。

word[7..12]，即 "ieaouq"。

题目来自leetcode3305。

大体步骤如下：

步骤一：滑动窗口与差分思想结合

1. 滑动窗口基础代码采用双指针（i为左指针，j为右指针）维护一个滑动窗口，确保窗口内的子字符串满足以下条件： • 包含所有元音字母（通过occur映射统计元音出现次数）。• 辅音数量至少为 m（m 是 k 或 k+1，通过差分计算最终结果）。
2. 差分思想优化通过计算 count(k) - count(k+1)，得到辅音数量恰好为 k 的子字符串数量。这里： • count(m) 返回辅音数量至少为 m 且包含所有元音的子字符串数量。• 差分后，仅保留辅音数量严格等于 k 的子字符串。

步骤二：滑动窗口的扩展与收缩

1. 窗口扩展（右指针 j 右移） • 目标：找到第一个满足条件的窗口（辅音数 ≥ m 且所有元音存在）。• 操作： ◦ 若当前字符是元音，更新 occur 映射中的出现次数。 ◦ 若为辅音，增加辅音计数 consonants。 ◦ 持续右移 j，直到窗口满足条件或超出字符串末尾。
2. 窗口收缩（左指针 i 右移） • 目标：调整窗口以寻找新的满足条件的子字符串。• 操作： ◦ 若左边界字符是元音，减少 occur 中对应元音的计数；若计数归零，从映射中删除该元音。 ◦ 若为辅音，减少辅音计数 consonants。
3. 统计有效子字符串 • 当窗口满足条件时，所有以 i 为左边界、右边界在 j 及之后的子字符串均有效，累加 n-j+1 到结果（即这些子字符串的数量）。

步骤三：示例分析 以输入 word = "ieaouqqieaouqq", k = 1 为例：

1. 计算 count(1) • 统计所有辅音数量 ≥ 1 且包含所有元音的子字符串。• 包含的辅音可能是 q 或 q 的组合，如 "ieaouq"（辅音 q）、"qieaou"（辅音 q）等。
2. 计算 count(2) • 统计辅音数量 ≥ 2 的子字符串。• 示例中无符合条件的子字符串，因为每个有效窗口仅含 1 个辅音。
3. 差分结果 • count(1) - count(2) = 3 - 0 = 3，得到恰好 1 个辅音的子字符串数量。

复杂度分析

1. 时间复杂度 • 滑动窗口的每个字符最多被左右指针各遍历一次，count(m) 的时间复杂度为 O(n)。• 总时间复杂度为两次 count 调用之和，即 O(n)。
2. 额外空间复杂度 • 使用固定大小的 occur 映射（最多存储 5 个元音）和常数变量，空间复杂度为 O(1)。

总结该算法通过滑动窗口高效统计满足条件的子字符串，并利用差分思想避免重复计算，最终在线性时间和常数空间内解决问题。

Go完整代码如下：

package main

import (
    "fmt"
)

func countOfSubstrings(word string, k int)int64 {
    vowels := map[byte]bool{'a': true, 'e': true, 'i': true, 'o': true, 'u': true}
    count := func(m int)int64 {
        n := len(word)
        var res int64 = 0
        consonants := 0
        occur := make(map[byte]int)
        for i, j := 0, 0; i < n; i++ {
            for j < n && (consonants < m || len(occur) < 5) {
                if vowels[word[j]] {
                    occur[word[j]]++
                } else {
                    consonants++
                }
                j++
            }
            if consonants >= m && len(occur) == 5 {
                res += int64(n - j + 1)
            }
            if vowels[word[i]] {
                occur[word[i]]--
                if occur[word[i]] == 0 {
                    delete(occur, word[i])
                }
            } else {
                consonants--
            }
        }
        return res
    }
    return count(k) - count(k+1)
}

func main() {
    word := "ieaouqqieaouqq"
    k := 1
    result := countOfSubstrings(word, k)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

defcount_of_substrings(word: str, k: int) -> int:
    vowels = {'a', 'e', 'i', 'o', 'u'}

    defcount(m: int) -> int:
        n = len(word)
        res = 0
        consonants = 0
        occur = {}
        i = 0
        j = 0

        while i < n:
            # 扩展右指针 j
            while j < n and (consonants < m orlen(occur) < 5):
                if word[j] in vowels:
                    occur[word[j]] = occur.get(word[j], 0) + 1
                else:
                    consonants += 1
                j += 1

            if consonants >= m andlen(occur) == 5:
                res += n - j + 1

            # 移动左指针 i，更新状态
            if word[i] in vowels:
                occur[word[i]] -= 1
                if occur[word[i]] == 0:
                    del occur[word[i]]
            else:
                consonants -= 1

            i += 1
        return res

    return count(k) - count(k + 1)


if __name__ == "__main__":
    word = "ieaouqqieaouqq"
    k = 1
    result = count_of_substrings(word, k)
    print(result)