LeetCode 题解工作台
统计美丽子字符串 II
给你一个字符串 s 和一个正整数 k 。 用 vowels 和 consonants 分别表示字符串中元音字母和辅音字母的数量。 如果某个字符串满足以下条件，则称其为 美丽字符串 ： vowels == consonants ，即元音字母和辅音字母的数量相等。 (vowels * consonant…
5
题型
1
代码语言
3
相关题
当前训练重点
困难 · 哈希·数学
答案摘要
function beautifulSubstrings(s: string, k: number): number { const l = pSqrt(k * 4);
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 哈希·数学 题型思路
题目描述
给你一个字符串 s 和一个正整数 k 。
用 vowels 和 consonants 分别表示字符串中元音字母和辅音字母的数量。
如果某个字符串满足以下条件，则称其为 美丽字符串 ：
vowels == consonants，即元音字母和辅音字母的数量相等。(vowels * consonants) % k == 0，即元音字母和辅音字母的数量的乘积能被k整除。
返回字符串 s 中 非空美丽子字符串 的数量。
子字符串是字符串中的一个连续字符序列。
英语中的 元音字母 为 'a'、'e'、'i'、'o' 和 'u' 。
英语中的 辅音字母 为除了元音字母之外的所有字母。
示例 1：
输入：s = "baeyh", k = 2 输出：2 解释：字符串 s 中有 2 个美丽子字符串。 - 子字符串 "baeyh"，vowels = 2（["a","e"]），consonants = 2（["y","h"]）。 可以看出字符串 "aeyh" 是美丽字符串，因为 vowels == consonants 且 vowels * consonants % k == 0 。 - 子字符串 "baeyh"，vowels = 2（["a","e"]），consonants = 2（["b","y"]）。 可以看出字符串 "baey" 是美丽字符串，因为 vowels == consonants 且 vowels * consonants % k == 0 。 可以证明字符串 s 中只有 2 个美丽子字符串。
示例 2：
输入：s = "abba", k = 1 输出：3 解释：字符串 s 中有 3 个美丽子字符串。 - 子字符串 "abba"，vowels = 1（["a"]），consonants = 1（["b"]）。 - 子字符串 "abba"，vowels = 1（["a"]），consonants = 1（["b"]）。 - 子字符串 "abba"，vowels = 2（["a","a"]），consonants = 2（["b","b"]）。 可以证明字符串 s 中只有 3 个美丽子字符串。
示例 3：
输入：s = "bcdf", k = 1 输出：0 解释：字符串 s 中没有美丽子字符串。
提示：
1 <= s.length <= 5 * 1041 <= k <= 1000s仅由小写英文字母组成。
解题思路
方法一：前缀和 + 哈希表 + 分解质因子
function beautifulSubstrings(s: string, k: number): number {
const l = pSqrt(k * 4);
const n = s.length;
let sum = n;
let ans = 0;
const counter = new Map();
counter.set(((l - 1) << 17) | sum, 1);
for (let i = 0; i < n; i++) {
const char = s[i];
const bit = (AEIOU_MASK >> (char.charCodeAt(0) - 'a'.charCodeAt(0))) & 1;
sum += bit * 2 - 1; // 1 -> 1 0 -> -1
const key = ((i % l) << 17) | sum;
ans += counter.get(key) || 0; // ans += cnt[(i%k,sum)]++
counter.set(key, (counter.get(key) ?? 0) + 1);
}
return ans;
}
const AEIOU_MASK = 1065233;
function pSqrt(n: number) {
let res = 1;
for (let i = 2; i * i <= n; i++) {
let i2 = i * i;
while (n % i2 == 0) {
res *= i;
n /= i2;
}
if (n % i == 0) {
res *= i;
n /= i;
}
}
if (n > 1) {
res *= n;
}
return res;
}
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for clear understanding of prefix sums and hash table usage.
- question_mark
Candidates should identify mathematical properties of the problem, such as the `x^2 % k == 0` condition.
- question_mark
The candidate should demonstrate an ability to optimize the brute force solution using efficient data structures.
常见陷阱
外企场景- error
Forgetting to account for the modulo condition in the product of vowels and consonants.
- error
Not optimizing the solution with prefix sums or hash tables, resulting in excessive time complexity.
- error
Confusing the conditions for a valid substring by incorrectly matching vowel and consonant counts.
进阶变体
外企场景- arrow_right_alt
Change the conditions to require a different relationship between vowels and consonants, such as vowels being greater than consonants.
- arrow_right_alt
Increase the string length and adjust `k` to test how the solution handles larger inputs.
- arrow_right_alt
Modify the problem to work with a different alphabet or consider case sensitivity.