2025-05-04：元音辅音字符串计数Ⅱ。用go语言，你有一个字符串 word 和一个非负整数 k。

要求计算并返回 word 中所有满足以下条件的子字符串的数量：

1.子字符串中的每种元音字母（‘a’、‘e’、‘i’、‘o’、‘u’）均至少出现过一次；

2.子字符串中辅音字母的总数正好是 k 个。

5 <= word.length <= 2 * 100000。

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

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

输入：word = “ieaouqqieaouqq”, k = 1。

输出：3。

解释：

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

word[0…5]，即 “ieaouq”。

word[6…11]，即 “qieaou”。

word[7…12]，即 “ieaouq”。

题目来自leetcode3306。

大体步骤如下：

1. 问题分析：需要统计满足两个条件的子字符串数目：包含所有元音至少一次，且辅音数正好为k。利用滑动窗口法分别计算辅音数至少k和k+1的情况，通过差值得到结果。

2. 元音判断：定义元音集合{‘a’,‘e’,‘i’,‘o’,‘u’}，快速判断字符是否为元音。

3. 滑动窗口初始化：使用双指针i（左）和j（右），初始化均为0。维护窗口内的辅音数和元音出现次数。

4. 窗口扩展（j指针移动）：对于每个i，尽可能右移j，直到窗口满足辅音数≥m且所有元音存在。此时，所有以i为左端点、右端点≥j的子字符串均满足条件，累加数目到结果。

5. 窗口收缩（i指针移动）：移动i时，更新窗口内辅音数和元音次数。若移出的是元音，减少其计数，若计数为0则移除；否则减少辅音数。

6. 结果计算：count(k)返回辅音数≥k的有效子串数目，count(k+1)返回≥k+1的数目。二者之差即为正好k的数目。

时间复杂度：O(n)。每个字符最多被i和j访问各一次，总体线性时间。

空间复杂度：O(1)。哈希表最多存储5个元音的出现次数，额外空间固定。

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 = {}
        j = 0
        for i in range(n):
            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
            # 缩小左边界
            if word[i] in vowels:
                occur[word[i]] -= 1
                if occur[word[i]] == 0:
                    del occur[word[i]]
            else:
                consonants -= 1
        return res

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


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