2062-统计字符串中的元音子字符串

子字符串 是字符串中的一个连续（非空）的字符序列。

元音子字符串 是 仅 由元音（'a'、'e'、'i'、'o' 和 'u'）组成的一个子字符串，且必须包含
全部五种 元音。

给你一个字符串 word ，统计并返回 word 中 元音子字符串的数目 。

示例 1：

**输入：** word = "aeiouu"
**输出：** 2
**解释：** 下面列出 word 中的元音子字符串（斜体加粗部分）：
- " _ **aeiou**_ u"
- " ** _aeiouu_** "

示例 2：

**输入：** word = "unicornarihan"
**输出：** 0
**解释：** word 中不含 5 种元音，所以也不会存在元音子字符串。

示例 3：

**输入：** word = "cuaieuouac"
**输出：** 7
**解释：** 下面列出 word 中的元音子字符串（斜体加粗部分）：
- "c _ **uaieuo**_ uac"
- "c _ **uaieuou**_ ac"
- "c _ **uaieuoua**_ c"
- "cu _ **aieuo**_ uac"
- "cu _ **aieuou**_ ac"
- "cu _ **aieuoua**_ c"
- "cua _ **ieuoua**_ c"

示例 4：

**输入：** word = "bbaeixoubb"
**输出：** 0
**解释：** 所有包含全部五种元音的子字符串都含有辅音，所以不存在元音子字符串。

提示：

• 1 <= word.length <= 100
• word 仅由小写英文字母组成

方法一：枚举 + 哈希集合

思路与算法

为了统计字符串中元音子字符串的数量，我们需要枚举字符串的所有子串，同时判断这些子串是否仅包含且全部包含所有元音。

我们可以先用哈希集合存储所有的元音字符，对于每个子串，我们只要判断它的所有字符组成的哈希集合是否和预处理生成的元音字符集相等即可。

而对于枚举子串，我们可以首先枚举字符串的左端点，然后自左端点开始从左至右枚举右端点，在枚举的同时将新加入的字符加入子串的哈希集合中，并与所有元音对应的哈希集合进行比较。与此同时，我们维护元音子字符串的数量，如果当前子串字符的哈希集合和所有元音的哈希集合相等，则当前子串为元音子串，我们将计数加上 1；反之则当前子串不为元音子串，计数不变。最终，我们返回该计数作为答案。

代码

[sol1-C++]

class Solution {
public:
    int countVowelSubstrings(string word) {
        int n = word.size();
        int res = 0;
        unordered_set<char> vowelset = {'a', 'e', 'i', 'o', 'u'};   // 所有元音对应的哈希集合
        for (int i = 0; i < n; ++i){
            // 枚举左端点
            unordered_set<char> charset;   // 子串对应的哈希集合
            for (int j = i; j < n; ++j){
                // 按顺序枚举右端点并更新子串哈希集合及比较
                charset.insert(word[j]);
                if (charset == vowelset){
                    ++res;
                }
            }
        }
        return res;
    }
};

[sol1-Python3]

class Solution:
    def countVowelSubstrings(self, word: str) -> int:
        n = len(word)
        res = 0
        vowelset = set("aeiou")   # 所有元音对应的哈希集合
        for i in range(n):
            # 枚举左端点
            charset = set()   # 子串对应的哈希集合
            for j in range(i, n):
                # 按顺序枚举右端点并更新子串哈希集合及比较
                charset.add(word[j])
                if charset == vowelset:
                    res += 1
        return res

复杂度分析

• 时间复杂度：O(n^2)，其中 n 为 word 的长度。即为枚举子串并判断是否为元音子字符串的时间复杂度。

• 空间复杂度：O(|\Sigma|)，其中 |\Sigma| 为字符集的大小。即为哈希集合的空间复杂度。