How do I efficiently count vowel substrings in this problem?

Use a sliding window combined with a hash table to track the vowels. As soon as all five vowels are in the window, count all substrings that start within it.

What if my string doesn't contain all five vowels?

In that case, the number of vowel substrings will be zero, as all five vowels are required for the substring to be valid.

What is the time complexity of this problem?

With the sliding window approach and hash table, the time complexity is O(n), where n is the length of the string.

What are common mistakes people make in this problem?

Common mistakes include failing to skip generating substrings with consonants and not efficiently counting substrings from valid windows.

Can I use other data structures for this problem?

While hash tables and sliding windows are optimal for this problem, other methods like brute force are less efficient for larger inputs.

#2062

Easy

auto_awesome哈希·表·结合·string

LeetCode 题解工作台

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

子字符串是字符串中的一个连续（非空）的字符序列。元音子字符串是仅由元音（ 'a' 、 'e' 、 'i' 、 'o' 和 'u' ）组成的一个子字符串，且必须包含全部五种元音。给你一个字符串 word ，统计并返回 word 中元音子字符串的数目。示例 1：输入： word …

哈希表字符串

题目描述

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

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

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

示例 1：

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

示例 2：

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

示例 3：

输入：word = "cuaieuouac"
输出：7
解释：下面列出 word 中的元音子字符串（斜体加粗部分）：
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"

示例 4：

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

提示：

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

lightbulb

解题思路

方法一：暴力枚举 + 哈希表

我们可以枚举子字符串的左端点 $i$ ，对于当前左端点，维护一个哈希表，记录当前子字符串中出现的元音字母，然后枚举右端点 $j$ ，如果当前右端点对应的字母不是元音字母，则跳出循环，否则将当前右端点对应的字母加入哈希表，如果哈希表中的元素个数为 $5$ ，则说明当前子字符串是一个元音子字符串，将结果加 $1$ 。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(C)$ 。其中 $n$ 为字符串 $word$ 的长度；而 $C$ 为字符集大小，本题中 $C=5$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def countVowelSubstrings(self, word: str) -> int:
        s = set("aeiou")
        ans, n = 0, len(word)
        for i in range(n):
            t = set()
            for c in word[i:]:
                if c not in s:
                    break
                t.add(c)
                ans += len(t) == 5
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate optimize the solution to avoid unnecessary checks for consonants?
question_mark
Does the candidate understand how to efficiently count substrings starting from any index in the window?
question_mark
Can the candidate effectively manage and update the window boundaries with a hash table?

warning

常见陷阱

外企场景

error
Forgetting to handle consonants and continuing substring generation unnecessarily.
error
Failing to properly update the window boundaries when encountering consonants.
error
Overcomplicating the counting process for substrings when the solution can be simplified using efficient window tracking.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider variants where the string contains no vowels and test the candidate's ability to handle edge cases.
arrow_right_alt
Test how the candidate handles cases where the string has multiple vowels, but not all five present.
arrow_right_alt
Explore the case where substrings must be of a specific length or meet other constraints.

help

常见问题

外企场景

继续练习

#2068 检查两个字符串是否几乎相等 #2053 数组中第 K 个独一无二的字符串 #2085 统计出现过一次的公共字符串