Count Beautiful Substrings II
You are given a string s
and a positive integer k
.
Let vowels
and consonants
be the number of vowels and consonants in a string.
A string is beautiful if:
vowels == consonants
.(vowels * consonants) % k == 0
, in other terms the multiplication ofvowels
andconsonants
is divisible byk
.
Return the number of non-empty beautiful substrings in the given string s
.
A substring is a contiguous sequence of characters in a string.
Vowel letters in English are 'a'
, 'e'
, 'i'
, 'o'
, and 'u'
.
Consonant letters in English are every letter except vowels.
Example 1:
Input: s = "baeyh", k = 2
Output: 2
Explanation: There are 2 beautiful substrings in the given string.
- Substring "baeyh", vowels = 2 (["a",e"]), consonants = 2 (["y","h"]).
You can see that string "aeyh" is beautiful as vowels == consonants and vowels * consonants % k == 0.
- Substring "baeyh", vowels = 2 (["a",e"]), consonants = 2 (["b","y"]).
You can see that string "baey" is beautiful as vowels == consonants and vowels * consonants % k == 0.
It can be shown that there are only 2 beautiful substrings in the given string.
Example 2:
Input: s = "abba", k = 1
Output: 3
Explanation: There are 3 beautiful substrings in the given string.
- Substring "abba", vowels = 1 (["a"]), consonants = 1 (["b"]).
- Substring "abba", vowels = 1 (["a"]), consonants = 1 (["b"]).
- Substring "abba", vowels = 2 (["a","a"]), consonants = 2 (["b","b"]).
It can be shown that there are only 3 beautiful substrings in the given string.
Example 3:
Input: s = "bcdf", k = 1
Output: 0
Explanation: There are no beautiful substrings in the given string.
Constraints:
1 <= s.length <= 5 * 104
1 <= k <= 1000
s
consists of only English lowercase letters.
解题思路
这题难的地方是在数论的部分,把 $x^2 \equiv 0 \pmod{k}$,找到一个 $m$ 等价变成 $x \equiv 0 \pmod{m}$ 还是很难想到的。
还是很容易知道是哈希表维护统计那一类题目。先将字符串构造出一个序列 $a$,如果 $\text{str}_i$ 是元音字母,则 $a_i = 1$,否则 $\text{str}_i$ 是辅音字母,则 $a_i = -1$。然后对序列 $a$ 求前缀和得到 $s$,当枚举到右端点 $r$,那么子数组的左端点 $l \in [0, r - 1]$ 就要满足 $s_r - s_l = 0$,即在左边找到满足 $s_l = s_r$ 的 $l$ 的数量。
还要满足另外一个条件,$\left(\frac{r-l}{2}\right)^2 \equiv 0 \pmod{k}$,式子等价于 $\left(\frac{r-l}{2}\right)^2 = x \cdot k, \, x \in \mathbb{Z}$。继续推有
\begin{align*}
\left(\frac{r-l}{2}\right)^2 &= x \cdot k \\
(r-l)^2 &= 4 x \cdot k \\
(r - l)^2 &\equiv 0 \pmod{4k}
\end{align*}
然后想到说能不能把左式的平方去掉,即找到一个 $m$,使得 $r - l \equiv 0 \pmod{m}$ 与上式的同余方程是等价的。对 $4k$ 进行质因数分解得到 $4k = p_1^{\alpha{1}} \cdot p_2^{\alpha{2}} \cdots p_n^{\alpha{n}}$,那么很明显对于每一项 $p_i^{\alpha{i}}$,$r-l$ 的质因数分解也必须含有 $p_i^{\beta{i}}$ 且 $2 \cdot \beta{i} \geq \alpha{i}$,即 $\beta{i} \geq \left\lceil \frac{\alpha{i}}{2} \right\rceil$。因此有 $m = p_1^{\left\lceil \frac{\alpha{1}}{2} \right\rceil} \cdot p_2^{\left\lceil \frac{\alpha{2}}{2} \right\rceil} \cdots p_n^{\left\lceil \frac{\alpha{n}}{2} \right\rceil}$,那么两个同余方程就可以等价了。
因此把哈希表开成两维,当枚举完右端点 $r$,维护 $\text{mp}[s_r][r \bmod m] \gets \text{mp}[s_r][r \bmod m] + 1$ 即可。由于 $s_r$ 可能是负数所以需要加上一个偏移量 $n$。
AC 代码如下,时间复杂度为 $O(\sqrt{k} + n)$:
class Solution {
public:
long long beautifulSubstrings(string str, int k) {
int n = str.size();
vector<int> s(n + 1);
set<char> st({'a', 'e', 'i', 'o', 'u'});
for (int i = 1; i <= n; i++) {
s[i] = s[i - 1];
if (st.count(str[i - 1])) s[i]++;
else s[i]--;
}
int m = 1;
k <<= 2;
for (int i = 2; i * i <= k; i++) {
if (k % i == 0) {
int s = 0;
while (k % i == 0) {
s++;
k /= i;
}
s = s + 1 >> 1;
while (s--) {
m *= i;
}
}
}
if (k > 1) m *= k;
vector<vector<int>> mp(n * 2 + 1, vector<int>(m));
long long ret = 0;
for (int i = 1; i <= n; i++) {
mp[s[i - 1] + n][(i - 1) % m]++;
ret += mp[s[i] + n][i % m];
}
return ret;
}
};
参考资料
子数组统计的套路【力扣周赛 373】:https://www.bilibili.com/video/BV19N411j7Dj/
赛事活动丨[第373 场周赛]式酱的解题报告:https://leetcode.cn/circle/discuss/k0kT9w/
- Substrings Beautiful Count IIsubstrings beautiful count ii substrings characters substrings unique string substrings leetcode removing minimum substrings diverse beautiful substrings 316g good cf autoregressive identifiers generating substrings codeforces substrings 104160b binary beautiful sequence bracket 1264d