统计美丽子字符串 II

题目

2949. 统计美丽子字符串 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 of vowels and consonants is divisible by k.

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 * 10^4
• 1 <= k <= 1000
• s consists of only English lowercase letters.

题解

方法一：

思路

符合条件的子串满足：

• 子串元音辅音字符个数都相同。这一点可以将元音设为1，辅音设为-1。求前缀和数组$ps$，当$ps_i = ps_j, i<j$时，$[i+1,j]$这个子串元辅音个数相同，所以只需要哈希统计前缀和出现的次数。
• 元辅音字符乘积是$k$的倍数。由于元辅音个数相同，对于合法子串长度为$L$，$\frac{L^2}{4} \bmod k = 0 \Rightarrow L^2 \bmod 4k = 0 \Rightarrow L \bmod r = 0$，对于$r$的计算，将$4k$进行质因数分解得到$4k = p_1^{e_{1}}p_2^{e_{2}}\cdots p_n^{e_{n}}$，$p_i$是第$i$个质数，$e_i$是$p_i$出现次数。$r = p_1^{\lceil \frac{e_{1}}{2} \rceil}p_2^{\lceil \frac{e_{2}}{2} \rceil}\cdots p_n^{\lceil \frac{e_{n}}{2} \rceil}$。我们记录当前下标$i\bmod r$，当存在$i \bmod r = j \bmod r, i<j$时，说明$[i+1,j]$子串长度是$r$的倍数，所以只需要哈希统计$i\bmod r$出现的次数。

我们需要哈希表同时统计前缀和与下标模$r$。

若当前遍历到下标$i$，查询以$i$作为右端点的所有合法子串数目，只需在哈希表中查找二元组$(ps_i, i \bmod k)$的个数。i下标也可做左端点，所以$(ps_i, i \bmod k)$在哈希表中的统计次数加1。

代码

class Solution {
public:
    using ll = long long;
    long long beautifulSubstrings(string s, int k) {
        vector<int> c(256, -1);
        for (char i:"aeiou"s) c[i] = 1;
        map<pair<int,int>,int> mp;
        int r = 1;
        k *= 4;
        for (int i=2; i*i<=k; i++) {
            int cnt = 0;
            while (k%i == 0) k/=i, cnt++;
            // cout << i << " " << cnt << "\n";
            for (int j=0; j<(cnt+1)/2; j++) r *= i;
        }
        r *= k;
        // cout << r << endl;
        long long ans = 0;
        int ps = 0, idx = 0;
        mp[{r-1, 0}] = 1;
        for (char i:s) {
            ps += c[i];
            ans += mp[{idx%r, ps}]++;
            idx++;
        }
        return ans;
    }
};