一夜暴富

3妹：2哥2哥，你有没有看到新闻， 有人中了2.2亿彩票大奖！
2哥 : 看到了，2.2亿啊， 一生一世也花不完。
3妹：为啥我就中不了呢，不开心呀不开心。
2哥 : 得了吧，你又不买彩票，还是脚踏实地的好~
3妹：小富靠勤，中富靠德，大富靠命， 可能是我命不好。
2哥 : 话说如果你有了钱，想要干嘛呀？
3妹：旅行，到处去旅行
2哥：就知道会有这一项， 我今天看到一个关于旅行的题目，让我也来考考你吧~

考考你

题目：

给你一个字符串 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 <= 1000
1 <= k <= 1000
s 仅由小写英文字母组成。

思路：

思考

详解见代码：

java代码：

public class Solution {
    private static final int AEIOU_MASK = 1065233;

    public int beautifulSubstrings(String s, int k) {
        k = pSqrt(k * 4);
        Map<Integer, Integer> cnt = new HashMap<>();
        int n = s.length();
        int sum = n; // 保证非负
        cnt.put((k - 1) << 16 | sum, 1); // 添加 (k-1, sum)
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int bit = (AEIOU_MASK >> (s.charAt(i) - 'a')) & 1;
            sum += bit * 2 - 1; // 1 -> 1    0 -> -1
            ans += cnt.merge((i % k) << 16 | sum, 1, Integer::sum) - 1; // ans += cnt[(i%k,sum)]++
        }
        return ans;
    }

    private int pSqrt(int n) {
        int res = 1;
        for (int i = 2; i * i <= n; i++) {
            int i2 = i * i;
            while (n % i2 == 0) {
                res *= i;
                n /= i2;
            }
            if (n % i == 0) {
                res *= i;
                n /= i;
            }
        }
        if (n > 1) {
            res *= n;
        }
        return res;
    }
}