class Solution {
public:
int beautifulSubstrings(string s, int k) {
}
};
100134. 统计美丽子字符串 I
给你一个字符串 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 仅由小写英文字母组成。原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 6.3 MB, 提交时间: 2023-11-27 07:02:22
func pSqrt(n int) int {
res := 1
for i := 2; i*i <= n; i++ {
i2 := i * i
for n%i2 == 0 {
res *= i
n /= i2
}
if n%i == 0 {
res *= i
n /= i
}
}
if n > 1 {
res *= n
}
return res
}
func beautifulSubstrings(s string, k int) (ans int) {
k = pSqrt(k * 4)
type pair struct{ i, sum int }
cnt := map[pair]int{{k - 1, 0}: 1} // k-1 和 -1 同余
sum := 0
const aeiouMask = 1065233
for i, c := range s {
bit := aeiouMask >> (c - 'a') & 1
sum += bit*2 - 1 // 1 -> 1 0 -> -1
p := pair{i % k, sum}
ans += cnt[p]
cnt[p]++
}
return
}
cpp 解法, 执行用时: 56 ms, 内存消耗: 6.9 MB, 提交时间: 2023-11-26 15:03:54
// 双指针解法
class Solution {
public:
int beautifulSubstrings(string s, int k) {
int res = 0;
for(int i = 0; i < s.size(); i++){
int a = 0, b = 0;
for(int j = i; j<s.size();j++){
if(s[j]=='a'||s[j]=='e'||s[j]=='i'||s[j]=='o'||s[j]=='u')a++;
else b++;
if((a*b)%k==0 && a==b)res++;
}
}
return res;
}
};
python3 解法, 执行用时: 1644 ms, 内存消耗: 16.1 MB, 提交时间: 2023-11-26 15:07:01
class Solution:
def beautifulSubstrings(self, s: str, k: int) -> int:
res = 0
n = len(s)
for i in range(n):
a, b = 0, 0
for j in range(i, n):
if s[j] in 'aeiou':
a += 1
else:
b += 1
if (a * b) % k == 0 and a == b:
res += 1
return res
java 解法, 执行用时: 20 ms, 内存消耗: 40.2 MB, 提交时间: 2023-11-26 15:08:49
class Solution {
public int beautifulSubstrings(String s, int k) {
int n = s.length();
int[] vowelCnt = new int[n + 1];
// 元音字母前缀和
for (int i = 1; i < n + 1; ++i) {
vowelCnt[i] = vowelCnt[i - 1] + (isVowel(s.charAt(i - 1)) ? 1 : 0);
}
int res = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int curVowelCnt = vowelCnt[j + 1] - vowelCnt[i];
int curConsonantCnt = j + 1 - i - curVowelCnt;
if (curVowelCnt == curConsonantCnt && curVowelCnt * curConsonantCnt % k == 0) {
++res;
}
}
}
return res;
}
private static final char[] vowels = new char[]{'a', 'o', 'e', 'i', 'u'};
private boolean isVowel(char c) {
for (char vowel : vowels) {
if (c == vowel) {
return true;
}
}
return false;
}
}