Hard

题目描述

给你一个字符串 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"，元音 = 2 (["a","e"])，辅音 = 2 (["y","h"])。
  可以看出字符串 "aeyh" 是美丽的，因为 vowels == consonants 且 vowels * consonants % k == 0。
- 子字符串 "baey"，元音 = 2 (["a","e"])，辅音 = 2 (["b","y"])。
  可以看出字符串 "baey" 是美丽的，因为 vowels == consonants 且 vowels * consonants % k == 0。
可以证明给定字符串中只有 2 个美丽子字符串。

示例 2：

输入：s = "abba", k = 1
输出：3
解释：给定字符串中有 3 个美丽子字符串。
- 子字符串 "ab"，元音 = 1 (["a"])，辅音 = 1 (["b"])。
- 子字符串 "ba"，元音 = 1 (["a"])，辅音 = 1 (["b"])。
- 子字符串 "abba"，元音 = 2 (["a","a"])，辅音 = 2 (["b","b"])。
可以证明给定字符串中只有 3 个美丽子字符串。

示例 3：

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

提示：

  • 1 <= s.length <= 5 * 10^4
  • 1 <= k <= 1000
  • s 仅由英文小写字母组成

解题思路

这道题要求统计满足两个条件的美丽子字符串：元音数等于辅音数，且元音数×辅音数能被k整除。

核心观察： 由于元音数等于辅音数，设为x，那么条件变为 x² % k == 0。关键是找出所有满足此条件的x值。

解题思路：

  1. 预处理候选值：找出所有满足 x² % k == 0 的x值。由于字符串长度有限，候选值数量不多。

  2. 前缀和 + 哈希表：对于每个候选值x，统计有多少子字符串的元音数和辅音数都等于x。

    • 用前缀和记录到当前位置的元音数减去辅音数的差值
    • 当差值为0且长度为2x时，说明元音数=辅音数=x

  3. 优化技巧：

    • 用哈希表记录每个前缀差值在不同位置的出现次数
    • 对于每个候选值x，只关心间隔为2x的位置对

算法步骤：

  1. 预计算所有满足 x² % k == 0 的x值
  2. 对每个x值，用滑动窗口或前缀和统计符合条件的子字符串
  3. 累加所有结果

时间复杂度主要取决于候选值数量和字符串长度的乘积。

代码实现

class Solution {
public:
    long long beautifulSubstrings(string s, int k) {
        int n = s.length();
        vector<int> candidates;
        
        // 找出所有满足 x^2 % k == 0 的 x
        for (int x = 1; x * x <= k; x++) {
            if ((long long)x * x % k == 0) {
                candidates.push_back(x);
            }
        }
        
        long long result = 0;
        
        // 对每个候选值 x 计算符合条件的子字符串
        for (int x : candidates) {
            unordered_map<int, int> count;
            int diff = 0; // 元音数 - 辅音数
            count[0] = 1; // 空前缀
            
            for (int i = 0; i < n; i++) {
                char c = s[i];
                if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                    diff++;
                } else {
                    diff--;
                }
                
                // 检查是否存在长度为 2*x 的子字符串
                if (i + 1 >= 2 * x) {
                    int prevDiff = diff;
                    // 回溯到 2*x 个字符之前的状态
                    for (int j = i; j > i - 2 * x; j--) {
                        char prevChar = s[j];
                        if (prevChar == 'a' || prevChar == 'e' || prevChar == 'i' || prevChar == 'o' || prevChar == 'u') {
                            prevDiff--;
                        } else {
                            prevDiff++;
                        }
                    }
                    if (prevDiff == diff && diff == 0) {
                        result++;
                    }
                }
            }
        }
        
        // 使用更高效的方法重新实现
        result = 0;
        for (int x : candidates) {
            unordered_map<pair<int, int>, int, hash<pair<int, int>>> mp;
            int vowels = 0;
            mp[{0, 0}] = 1;
            
            for (int i = 0; i < n; i++) {
                if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u') {
                    vowels++;
                }
                
                int consonants = i + 1 - vowels;
                int diff = vowels - consonants;
                int pos = (i + 1) % (2 * x);
                
                if (mp.count({diff, pos})) {
                    result += mp[{diff, pos}];
                }
                mp[{diff, pos}]++;
            }
        }
        
        return result;
    }
};

class Solution:
    def beautifulSubstrings(self, s: str, k: int) -> int:
        n = len(s)
        candidates = []
        
        # 找出所有满足 x^2 % k == 0 的 x
        x = 1
        while x * x <= k:
            if (x * x) % k == 0:
                candidates.append(x)
            x += 1
        
        result = 0
        vowels_set = set('aeiou')
        
        # 对每个候选值 x 计算符合条件的子字符串
        for x in candidates:
            # 使用哈希表记录 (差值, 位置模2x) 的出现次数
            count_map = {}
            vowels = 0
            count_map[(0, 0)] = 1
            
            for i in range(n):
                if s[i] in vowels_set:
                    vowels += 1
                
                consonants = i + 1 - vowels
                diff = vowels - consonants
                pos = (i + 1) % (2 * x)
                
                key = (diff, pos)
                if key in count_map:
                    result += count_map[key]
                
                count_map[key] = count_map.get(key, 0) + 1
        
        return result

public class Solution {
    public long BeautifulSubstrings(string s, int k) {
        int n = s.Length;
        List<int> candidates = new List<int>();
        
        // 找出所有满足 x^2 % k == 0 的 x
        for (int x = 1; x * x <= k; x++) {
            if ((long)x * x % k == 0) {
                candidates.Add(x);
            }
        }
        
        long result = 0;
        HashSet<char> vowels = new HashSet<char> {'a', 'e', 'i', 'o', 'u'};
        
        // 对每个候选值 x 计算符合条件的子字符串
        foreach (int x in candidates) {
            Dictionary<(int, int), int> countMap = new Dictionary<(int, int), int>();
            int vowelCount = 0;
            countMap[(0, 0)] = 1;
            
            for (int i = 0; i < n; i++) {
                if (vowels.Contains(s[i])) {
                    vowelCount++;
                }
                
                int consonants = i + 1 - vowelCount;
                int diff = vowelCount - consonants;
                int pos = (i + 1) % (2 * x);
                
                var key = (diff, pos);
                if (countMap.ContainsKey(key)) {
                    result += countMap[key];
                }
                
                if (countMap.ContainsKey(key)) {
                    countMap[key]++;
                } else {
                    countMap[key] = 1;
                }
            }
        }
        
        return result;
    }
}

var beautifulSubstrings = function(s, k) {
    const vowels = new Set(['a', 'e', 'i', 'o', 'u']);
    const n = s.length;
    let count = 0;
    
    // Find the minimum length where vowels^2 % k == 0
    let minLen = 1;
    while ((minLen * minLen) % (4 * k) !== 0) {
        minLen++;
    }
    
    // For each possible remainder when divided by minLen
    for (let rem = 0; rem < minLen; rem++) {
        // Map to store count of each balance at positions with same remainder
        const balanceCount = new Map();
        balanceCount.set(0, 1); // Empty prefix
        
        let balance = 0; // vowels - consonants
        
        for (let i = 0; i < n; i++) {
            if (vowels.has(s[i])) {
                balance++;
            } else {
                balance--;
            }
            
            if (i % minLen === rem) {
                count += balanceCount.get(balance) || 0;
                balanceCount.set(balance, (balanceCount.get(balance) || 0) + 1);
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(C × n)，其中 C 是候选值数量（满足 x² % k == 0 的 x 值），n 是字符串长度。候选值数量通常很小。
空间复杂度O(C × x_max)，主要用于存储哈希表，其中 x_max 是最大的候选值。