给你一个字符串 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 个美丽子字符串。
- 子字符串 "b_aeyh_"，vowels = 2（["a","e"]），consonants = 2（["y","h"]）。
可以看出字符串 "aeyh" 是美丽字符串，因为 vowels == consonants 且 vowels * consonants % k == 0 。
- 子字符串 "_baey_h"，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 个美丽子字符串。
- 子字符串 "_ab_ba"，vowels = 1（["a"]），consonants = 1（["b"]）。
- 子字符串 "ab_ba_"，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 * 10^41 <= k <= 1$0$s仅由小写英文字母组成。
解法 分解质因子+前缀和+哈希表
把元音视作 1 1 1，辅音视作 − 1 -1 −1 。「元音字母和辅音字母的数量相等」就等价于：。注意这种子数组的长度一定是偶数，因为元音辅音数量相等。
设子数组的长度为 L L L 。由于元音辅音数量相等，所以元音辅音数量都等于 L 2 \dfrac{L}{2} 2L ，所以「元音字母和辅音字母的数量的乘积能被 k k k 整除」等价于
( L 2 ) 2 m o d k = 0 \left(\dfrac{L}{2}\right)^2 \bmod k = 0 (2L)2modk=0
这等价于
L 2 m o d ( 4 k ) = 0 L^2 \bmod (4k) = 0 L2mod(4k)=0
这个平方很烦人，如果能去掉平方就好做了。
这里得来点数学。我们来研究下，如果一个数 L L L 的平方能被 n n n 整除，意味着什么？
- 假设 n n n 是一个质数，例如 3 3 3，那么 L L L 必须包含质因子 3 3 3 ，此时问题就变成了：判断 L L L 能不能被 3 3 3 整除。我们把平方去掉了！
- 如果 n n n 是一个质数 $p 的 e e e 次幂呢？分类讨论：
- 如果 e e e是偶数，比如 n = 3 4 n=3^4 n=34 ，那么 L L L 必须包含因子 3 2 3^2 32 ，才能使得 L 2 L^2 L2 能被 n n n 整除。此时问题就变成了：判断 L L L 能不能被 3 2 3^2 32 整除。
- 如果 e e e 是奇数，比如 n = 3 5 n=3^5 n=35 ，那么 L L L 必须包含因子 3 3 3^3 33 ，才能使得 L 2 L^2 L2 能被 n n n 整除。此时问题就变成了：判断 L L L 能不能被 3 3 3^3 33 整除。
所以 L L L 必须包含因子 p r p^r pr ，其中 r = ⌈ e 2 ⌉ = ⌊ e + 1 2 ⌋ r=\left\lceil\dfrac{e}{2}\right\rceil = \left\lfloor\dfrac{e+1}{2}\right\rfloor r=⌈2e⌉=⌊2e+1⌋ 。
- 如果 n n n 可以分解出多个质因子，只需要把每个质因子及其幂次按照上面的方法处理，然后再相乘，就得到 L L L 必须包含什么因子。
继续
把 4 4 4 按照上述方法计算，设 L L L 必须包含因子 k ′ k' k′ 。现在问题变成，有多少个和为 0 0 0 的子数组，其长度是 k ′ k' k′ 的倍数？
设子数组的下标范围为 [ j , i ) [j,i) [j,i) ，那么其长度 L = i − j L=i-j L=i−j ，则有
( i − j ) m o d k ′ = 0 (i-j)\bmod k' = 0 (i−j)modk′=0
等价于
i m o d k ′ = j m o d k ′ i \bmod k' = j\bmod k' imodk′=jmodk′
对于元素和来说，相当于 s [ i ] − s [ j ] = 0 s[i]-s[j] = 0 s[i]−s[j]=0 ，即
s [ i ] = s [ j ] s[i] = s[j] s[i]=s[j]
我们需要同时满足这两个条件（下标模 k ′ k' k′ 相等， s s s 值相等），这可以一并用哈希表解决。哈希表的 k e y key key 是一个 p a i r pair pair ： ( i m o d k ′ , s [ i ] ) (i\bmod k', s[i]) (imodk′,s[i]) ，哈希表的 v a l u e value value 是这个 p a i r pair pair 的出现次数。
代码实现时，前缀和数组可以用一个变量表示。
代码实现时，可以把 aeiou 压缩成一个二进制数，从而快速判断字母是否为元音。
class Solution {
private:
int pSqrt(int n) {
int ans = 1;
for (int i = 2; i * i <= n; ++i) {
int i2 = i * i;
while (n % i2 == 0) { // 质因数分解
ans *= i; // L必须包含一个i^1
n /= i2;
}
if (n % i == 0) { // 如果n包含某个质数的奇次幂
ans *= i;
n /= i;
}
}
if (n > 1) ans *= n; // 剩下的最后1个质因子
return ans;
}
struct PairHash {
template<typename T1, typename T2>
size_t operator() (const pair<T1, T2> &p) const {
auto v1 = std::hash<T1>{}(p.first);
auto v2 = std::hash<T2>{}(p.second);
return v1 ^ v2;
}
};
unordered_map<pair<int, int>, int, PairHash> cnt; //ok
public:
int beautifulSubstrings(string s, int k) {
k = pSqrt(k * 4); // 4k的质因数分解，求出L必须包含的因子值（多个质因子的幂次的乘积）
const int aeiouMask = 1065233;
cnt[ pair<int, int>{ k - 1, 0} ] = 1; // k-1和1同余
int sum = 0;
int ans = 0;
for (int i = 0; i < s.size(); ++i) {
char c = s[i];
int bit = aeiouMask >> (c - 'a') & 1;
sum += bit * 2 - 1; // 1->1, 0->-1
auto p = pair{i % k, sum};
ans += (long long)cnt[p];
++cnt[p];
}
return ans;
}
};
复杂度分析：
- 时间复杂度： O ( n + k ) \mathcal{O}(n + \sqrt k) O(n+k ) ，其中 n n n 为 nums \textit{nums} nums 的长度。
- 空间复杂度： O ( n ) \mathcal{O}(n) O(n) 。