Medium

题目描述

给你一个字符串 s 和一个正整数 k。

设 vowels 和 consonants 分别是字符串中元音和辅音的数量。

如果字符串满足以下条件，则该字符串是 美丽的：

  • vowels == consonants，即元音数量等于辅音数量。
  • (vowels * consonants) % k == 0，即元音数量与辅音数量的乘积能被 k 整除。

返回字符串 s 中 非空美丽子字符串 的数量。

子字符串 是字符串中的一个连续字符序列。

英文中的元音字母是 'a', 'e', 'i', 'o', 'u'。

英文中的辅音字母是除了元音字母之外的所有字母。

示例 1：

输入：s = "baeyh", k = 2
输出：2
解释：给定字符串中有 2 个美丽子字符串。
- 子字符串 "aeyh"，vowels = 2 (["a","e"])，consonants = 2 (["y","h"])。
可以看出字符串 "aeyh" 是美丽的，因为 vowels == consonants 且 vowels * consonants % k == 0。
- 子字符串 "baey"，vowels = 2 (["a","e"])，consonants = 2 (["b","y"])。
可以看出字符串 "baey" 是美丽的，因为 vowels == consonants 且 vowels * consonants % k == 0。

示例 2：

输入：s = "abba", k = 1
输出：3
解释：给定字符串中有 3 个美丽子字符串。
- 子字符串 "ab"，vowels = 1 (["a"])，consonants = 1 (["b"])。
- 子字符串 "ba"，vowels = 1 (["a"])，consonants = 1 (["b"])。
- 子字符串 "abba"，vowels = 2 (["a","a"])，consonants = 2 (["b","b"])。

示例 3：

输入：s = "bcdf", k = 1
输出：0
解释：给定字符串中没有美丽子字符串。

提示：

  • 1 <= s.length <= 1000
  • 1 <= k <= 1000
  • s 仅由英文小写字母组成

解题思路

解题思路

这道题要求找出满足两个条件的美丽子字符串数量：

  1. 元音数量等于辅音数量
  2. 元音数量与辅音数量的乘积能被 k 整除

方法一：暴力枚举（推荐）

最直观的思路是枚举所有可能的子字符串，然后检查每个子字符串是否满足美丽条件。

具体步骤：

  1. 使用双重循环遍历所有可能的子字符串起始位置 i 和结束位置 j
  2. 对于每个子字符串，统计其中的元音和辅音数量
  3. 检查是否满足 vowels == consonants 且 (vowels * consonants) % k == 0
  4. 如果满足条件，计数器加一

优化技巧

在内层循环中，我们可以边扩展子字符串边统计元音和辅音数量，这样避免了重复计算。每当我们将一个新字符加入当前子字符串时，只需要判断这个字符是元音还是辅音，然后更新相应的计数器。

时间复杂度虽然是 O(n²)，但由于题目约束较小（n ≤ 1000），这个解法完全可行。

代码实现

class Solution {
public:
    int beautifulSubstrings(string s, int k) {
        int n = s.length();
        int count = 0;
        
        auto isVowel = [](char c) {
            return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
        };
        
        for (int i = 0; i < n; i++) {
            int vowels = 0, consonants = 0;
            for (int j = i; j < n; j++) {
                if (isVowel(s[j])) {
                    vowels++;
                } else {
                    consonants++;
                }
                
                if (vowels == consonants && (vowels * consonants) % k == 0) {
                    count++;
                }
            }
        }
        
        return count;
    }
};

class Solution:
    def beautifulSubstrings(self, s: str, k: int) -> int:
        n = len(s)
        count = 0
        vowels_set = set('aeiou')
        
        for i in range(n):
            vowels = 0
            consonants = 0
            for j in range(i, n):
                if s[j] in vowels_set:
                    vowels += 1
                else:
                    consonants += 1
                
                if vowels == consonants and (vowels * consonants) % k == 0:
                    count += 1
        
        return count

public class Solution {
    public int BeautifulSubstrings(string s, int k) {
        int n = s.Length;
        int count = 0;
        HashSet<char> vowelsSet = new HashSet<char> {'a', 'e', 'i', 'o', 'u'};
        
        for (int i = 0; i < n; i++) {
            int vowels = 0, consonants = 0;
            for (int j = i; j < n; j++) {
                if (vowelsSet.Contains(s[j])) {
                    vowels++;
                } else {
                    consonants++;
                }
                
                if (vowels == consonants && (vowels * consonants) % k == 0) {
                    count++;
                }
            }
        }
        
        return count;
    }
}

var beautifulSubstrings = function(s, k) {
    const isVowel = (c) => 'aeiou'.includes(c);
    let count = 0;
    
    for (let i = 0; i < s.length; i++) {
        let vowels = 0;
        let consonants = 0;
        
        for (let j = i; j < s.length; j++) {
            if (isVowel(s[j])) {
                vowels++;
            } else {
                consonants++;
            }
            
            if (vowels === consonants && (vowels * consonants) % k === 0) {
                count++;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)双重循环遍历所有子字符串，n 为字符串长度
空间复杂度O(1)只使用常量额外空间存储计数器和元音字符集合