class Solution {
public:
long long beautifulSubstrings(string s, int k) {
}
};
100132. 统计美丽子字符串 II
给你一个字符串 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 仅由小写英文字母组成。原站题解
python3 解法, 执行用时: 356 ms, 内存消耗: 20.2 MB, 提交时间: 2023-11-26 15:14:38
'''
分解质因子+前缀和+哈希表
'''
class Solution:
def beautifulSubstrings(self, s: str, k: int) -> int:
k = self.sqrt(k * 4)
cnt = Counter([(k - 1, 0)]) # k-1 和 -1 同余
ans = pre_sum = 0
for i, c in enumerate(s):
pre_sum += 1 if c in "aeiou" else -1
p = (i % k, pre_sum)
ans += cnt[p]
cnt[p] += 1
return ans
def sqrt(self, n: int) -> int:
res = 1
i = 2
while i * i <= n:
i2 = i * i
while n % i2 == 0:
res *= i
n //= i2
if n % i == 0:
res *= i
n //= i
i += 1
if n > 1:
res *= n
return res
golang 解法, 执行用时: 52 ms, 内存消耗: 8.1 MB, 提交时间: 2023-11-26 15:15:09
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 int64) {
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 += int64(cnt[p])
cnt[p]++
}
return
}
java 解法, 执行用时: 93 ms, 内存消耗: 44.2 MB, 提交时间: 2023-11-26 15:15:35
class Solution {
private int pSqrt(int k) {
int res = 1;
for (int i = 2; i * i <= k; i++) {
int i2 = i * i;
while (k % i2 == 0) {
res *= i;
k /= i2;
}
if (k % i == 0) {
res *= i;
k /= i;
}
}
if (k > 1) {
res *= k;
}
return res;
}
public long beautifulSubstrings(String s, int k) {
int sqrtK = pSqrt(4 * k);
Map<String, Integer> pair2Count = new HashMap<>();
pair2Count.put(sqrtK - 1 + " " + 0, 1);
int preSum = 0;
int count = 0;
for (int i = 0; i < s.length(); i++) {
if (isVowel(s.charAt(i))) {
preSum--;
} else {
preSum++;
}
String key = (i % sqrtK) + " " + preSum;
count += pair2Count.getOrDefault(key, 0);
pair2Count.put(key, pair2Count.getOrDefault(key, 0) + 1);
}
return count;
}
private boolean isVowel(char c) {
c = Character.toLowerCase(c);
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
}