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

🟢   🔖  哈希表 字符串  🔗 力扣 LeetCode

题目

A substring is a contiguous (non-empty) sequence of characters within a string.

A vowel substring is a substring that only consists of vowels ('a', 'e', 'i', 'o', and 'u') and has all five vowels present in it.

Given a string word, return the number ofvowel substrings in word.

Example 1:

Input: word = "aeiouu"

Output: 2

Explanation: The vowel substrings of word are as follows (underlined):

• "aeiou u"
• "aeiouu "

Example 2:

Input: word = "unicornarihan"

Output: 0

Explanation: Not all 5 vowels are present, so there are no vowel substrings.

Example 3:

Input: word = "cuaieuouac"

Output: 7

Explanation: The vowel substrings of word are as follows (underlined):

• "c** uaieuo** uac"
• "c** uaieuou** ac"
• "c** uaieuoua** c"
• "cu** aieuo** uac"
• "cu** aieuou** ac"
• "cu** aieuoua** c"
• "cua** ieuoua** c"

Constraints:

• 1 <= word.length <= 100
• word consists of lowercase English letters only.

题目大意

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

元音子字符串 是 仅 由元音（'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 仅由小写英文字母组成

解题思路

核心条件：

• 子字符串必须仅包含元音字母。
• 子字符串中必须包含 a, e, i, o, u，且至少出现一次。

滑动窗口：

• 使用滑动窗口可以高效地检查一个连续的子字符串是否符合条件。
• 在每次扩展窗口的过程中，更新一个数组来记录窗口内每个元音字母的出现次数。

1. 初始化变量：

   • vowels：一个哈希表，用来快速判断字符是否为元音，并映射其索引。
   • freq：一个长度为 5 的数组，用来记录 a, e, i, o, u 在窗口中的频次。
   • left 和 right：滑动窗口的左右边界。
   • count：用于记录符合条件的子字符串个数。

2. 滑动窗口逻辑：

   • 如果 right 指向的字符是元音：
     • 更新窗口内元音字符的频次。
     • 检查窗口内是否包含所有元音字符。如果包含，则 count 增加。
     • 移动 right 扩大窗口。
   • 如果 right 指向的字符不是元音：
     • 窗口无效，需要重置窗口。
     • 将 left 和 right 移动到 left + 1，并清空 freq。

3. 返回最终结果。

复杂度分析

• 时间复杂度：O(n)，窗口右边界最多移动 n 次，左边界最多移动 n 次。
• 空间复杂度：O(1)，使用了一个长度为 5 的数组。

代码

/**
 * @param {string} word
 * @return {number}
 */
var countVowelSubstrings = function (word) {
	const vowels = {
		a: 0,
		e: 1,
		i: 2,
		o: 3,
		u: 4
	};
	let freq = new Array(5).fill(0);
	let count = 0;
	let left = 0;
	let right = 0;

	while (left <= word.length - 5) {
		const cur = word[right];
		if (vowels[cur] !== undefined) {
			freq[vowels[cur]]++;
			if (
				freq[0] > 0 &&
				freq[1] > 0 &&
				freq[2] > 0 &&
				freq[3] > 0 &&
				freq[4] > 0
			) {
				count++;
			}
			right++;
		} else {
			left++;
			right = left;
			freq.fill(0);
		}
	}

	return count;
};

相关题目

题号	标题	题解	标签	难度	力扣
792	匹配子序列的单词数		字典树 数组 哈希表 4+	🟠	🀄️ 🔗
992	K 个不同整数的子数组		数组 哈希表 计数 1+	🔴	🀄️ 🔗
1513	仅含 1 的子串数		数学 字符串	🟠	🀄️ 🔗
1839	所有元音按顺序排布的最长子字符串		字符串 滑动窗口	🟠	🀄️ 🔗
2262	字符串的总引力	[✓]	哈希表 字符串 动态规划	🔴	🀄️ 🔗
3305	元音辅音字符串计数 I		哈希表 字符串 滑动窗口	🟠	🀄️ 🔗
3306	元音辅音字符串计数 II		哈希表 字符串 滑动窗口	🟠	🀄️ 🔗