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

福大大架构师每日一题

发布于 2025-05-04 10:27:51

7500

代码可运行

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

运行总次数：0

代码可运行

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

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 = {}
        j = 0
        for i inrange(n):
            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
            # 缩小左边界
            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)