LeetCode 题解工作台
统计美丽子字符串 I
给你一个字符串 s 和一个正整数 k 。 用 vowels 和 consonants 分别表示字符串中元音字母和辅音字母的数量。 如果某个字符串满足以下条件，则称其为 美丽字符串 ： vowels == consonants ，即元音字母和辅音字母的数量相等。 (vowels * consonant…
6
题型
6
代码语言
3
相关题
当前训练重点
中等 · 哈希·数学
答案摘要
我们在 $[0, n)$ 范围内枚举子字符串的起始位置 ，在 $[i, n)$ 范围内枚举子字符串的结束位置 ，统计子字符串 $s[i \dots j]$ 中元音字母和辅音字母的数量，判断其是否为美丽字符串，如果是，则将答案加 。 时间复杂度 ，其中 是字符串的长度。空间复杂度 。
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 <= 10001 <= k <= 1000s仅由小写英文字母组成。
解题思路
方法一：枚举
我们在 范围内枚举子字符串的起始位置 ，在 范围内枚举子字符串的结束位置 ，统计子字符串 中元音字母和辅音字母的数量，判断其是否为美丽字符串，如果是，则将答案加 。
时间复杂度 ，其中 是字符串的长度。空间复杂度 。
class Solution:
def beautifulSubstrings(self, s: str, k: int) -> int:
n = len(s)
vs = set("aeiou")
ans = 0
for i in range(n):
vowels = 0
for j in range(i, n):
vowels += s[j] in vs
consonants = j - i + 1 - vowels
if vowels == consonants and vowels * consonants % k == 0:
ans += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Does the candidate show an understanding of hash table use in optimization?
- question_mark
Is the candidate capable of correctly identifying when a substring satisfies the condition?
- question_mark
How well does the candidate handle the substring enumeration efficiently?
常见陷阱
外企场景- error
Overcalculating vowel and consonant counts for every substring from scratch, which leads to a higher time complexity.
- error
Failing to account for edge cases, such as when there are no vowels or consonants.
- error
Incorrectly interpreting the problem's condition, leading to counting invalid substrings.
进阶变体
外企场景- arrow_right_alt
Modify the problem by changing the condition to check for a different mathematical property, such as the sum of vowels and consonants modulo k.
- arrow_right_alt
Extend the problem to count substrings that are beautiful and also palindromes.
- arrow_right_alt
Change the problem to find the longest beautiful substring instead of counting all beautiful substrings.