Medium

题目描述

给你一个字符串 word 和一个非负整数 k。

返回 word 的子串中包含每个元音字母（‘a’, ’e’, ‘i’, ‘o’, ‘u’）至少一次且恰好包含 k 个辅音字母的子串总数。

示例 1：

输入：word = "aeioqq", k = 1
输出：0
解释：没有包含所有元音字母的子串。

示例 2：

输入：word = "aeiou", k = 0
输出：1
解释：唯一包含所有元音字母且零个辅音字母的子串是 word[0..4]，即 "aeiou"。

示例 3：

输入：word = "ieaouqqieaouqq", k = 1
输出：3
解释：包含所有元音字母和一个辅音字母的子串有：
- word[0..5]，即 "ieaouq"
- word[6..11]，即 "qieaou"  
- word[7..12]，即 "ieaouq"

约束条件：

  • 5 <= word.length <= 250
  • word 仅由小写英文字母组成
  • 0 <= k <= word.length - 5

提示：

  • 使用哈希表并检查所有子串。

解题思路

这道题需要找到包含所有5个元音字母至少一次且恰好包含k个辅音字母的子串数量。

解题思路

方法一：暴力枚举（推荐） 由于字符串长度较小（≤250），我们可以枚举所有可能的子串，对每个子串检查是否满足条件：

  1. 包含所有5个元音字母（a,e,i,o,u）至少一次
  2. 恰好包含k个辅音字母

具体实现：

  • 使用双重循环枚举所有子串的起始和结束位置
  • 对每个子串维护元音字母计数和辅音字母计数
  • 检查是否所有元音字母都出现过且辅音字母数量恰好为k

方法二：滑动窗口优化 虽然可以考虑滑动窗口，但由于需要同时满足"包含所有元音"和"恰好k个辅音"两个条件，窗口的伸缩逻辑较为复杂，在数据规模较小的情况下，暴力解法更加直观易懂。

时间复杂度分析：由于字符串长度最大为250，O(n²)的复杂度是可以接受的。

代码实现

class Solution {
public:
    int countOfSubstrings(string word, int k) {
        int n = word.length();
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            unordered_set<char> vowels;
            int consonants = 0;
            
            for (int j = i; j < n; j++) {
                char c = word[j];
                if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                    vowels.insert(c);
                } else {
                    consonants++;
                }
                
                // 如果辅音字母数超过k，后续子串都不可能满足条件
                if (consonants > k) break;
                
                // 检查是否满足条件
                if (vowels.size() == 5 && consonants == k) {
                    count++;
                }
            }
        }
        
        return count;
    }
};

class Solution:
    def countOfSubstrings(self, word: str, k: int) -> int:
        n = len(word)
        count = 0
        
        for i in range(n):
            vowels = set()
            consonants = 0
            
            for j in range(i, n):
                c = word[j]
                if c in 'aeiou':
                    vowels.add(c)
                else:
                    consonants += 1
                
                # 如果辅音字母数超过k，后续子串都不可能满足条件
                if consonants > k:
                    break
                
                # 检查是否满足条件
                if len(vowels) == 5 and consonants == k:
                    count += 1
        
        return count

public class Solution {
    public int CountOfSubstrings(string word, int k) {
        int n = word.Length;
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            HashSet<char> vowels = new HashSet<char>();
            int consonants = 0;
            
            for (int j = i; j < n; j++) {
                char c = word[j];
                if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                    vowels.Add(c);
                } else {
                    consonants++;
                }
                
                // 如果辅音字母数超过k，后续子串都不可能满足条件
                if (consonants > k) break;
                
                // 检查是否满足条件
                if (vowels.Count == 5 && consonants == k) {
                    count++;
                }
            }
        }
        
        return count;
    }
}

var countOfSubstrings = function(word, k) {
    const vowels = new Set(['a', 'e', 'i', 'o', 'u']);
    let count = 0;
    
    for (let i = 0; i < word.length; i++) {
        let vowelSet = new Set();
        let consonants = 0;
        
        for (let j = i; j < word.length; j++) {
            if (vowels.has(word[j])) {
                vowelSet.add(word[j]);
            } else {
                consonants++;
            }
            
            if (vowelSet.size === 5 && consonants === k) {
                count++;
            }
            
            if (consonants > k) {
                break;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n²)
空间复杂度O(1)

其中 n 为字符串长度。时间复杂度为 O(n²)，因为需要枚举所有可能的子串；空间复杂度为 O(1)，只使用了常数额外空间（哈希集合最多存储5个元音字母）。

相关题目