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-*-

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

    def count(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 or len(occur) < 5):
                if word[j] in vowels:
                    occur[word[j]] = occur.get(word[j], 0) + 1
                else:
                    consonants += 1
                j += 1

            if consonants >= m and len(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)