统计美丽子字符串 II

标签: 哈希表数学字符串数论前缀和

难度: Hard

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

Submission

运行时间: 160 ms

内存: 19.0 MB

class Solution:
    def beautifulSubstrings(self, s: str, k: int) -> int:
        #v=c,v*v%k==0 =>  v%k==0或v*a=k =>v是x的倍数,x=a1^(b1+1//2)*..
        p=2
        x=1
        while p<k:
            b=0
            while k%p==0:
                k//=p
                b+=1
            x*=pow(p,(b+1)//2)  
            p+=1
        if k>1:x*=k
        ans=0
        v=c=0
        a='aeiou'
        m=defaultdict(lambda :defaultdict(int))
        m[0][0]=1
        for y in s:
            if y in a:v+=1
            else:c+=1
            d=v-c
            ans+=m[d][v%x]
            m[d][v%x]+=1
        return ans

Explain

这个题解利用了数学和哈希表的方法来统计美丽子字符串。首先，它通过分解k以找到一个最小的x，使得任意v满足v*v%k==0时，v必须是x的倍数。接着，使用一个双层哈希表m来记录差值(d=v-c)和v对x取模的结果的出现次数。遍历字符串s，对于每个字符，根据其是否是元音来更新v和c的值，计算当前的差值d和v对x的模，然后查找哈希表中已有的符合条件的前缀和，并更新答案。最后，更新哈希表以包括当前的前缀和状态。

时间复杂度: O(n)

空间复杂度: O(n*x)

class Solution:
    def beautifulSubstrings(self, s: str, k: int) -> int:
        p = 2
        x = 1
        # 分解k以找到x
        while p < k:
            b = 0
            while k % p == 0:
                k //= p
                b += 1
            x *= pow(p, (b + 1) // 2)
            p += 1
        if k > 1: x *= k
        ans = 0
        v = c = 0
        vowels = 'aeiou'
        # 使用双层哈希表记录差值和模的组合
        m = defaultdict(lambda: defaultdict(int))
        m[0][0] = 1
        for y in s:
            if y in vowels: v += 1
            else: c += 1
            d = v - c
            # 计算当前前缀和的美丽子字符串数量
            ans += m[d][v % x]
            # 更新哈希表
            m[d][v % x] += 1
        return ans

Explore

在题解中，分解整数k并找到最小的x是为了简化 `(vowels * consonants) % k == 0` 的检查过程。这个条件要求元音和辅音的数量乘积能够整除k。通过分解k为其质因数的乘积，我们可以发现当k可以被某个数v整除时，v必须包含k质因数分解中每个质数的至少一半的幂次。举例来说，如果k是12，其质因数分解为2^2 * 3，那么任何能整除12的v，必须至少包含2和3，其中2至少是2的1次方。这样，我们可以通过计算这个最小x，来确保当元音和辅音的数量的差值d等于0时，它们的乘积能整除k。这种数学处理能有效减少需要检查的情况，从而优化了算法性能。

在算法中，`vowels == consonants`条件转化为检查元音和辅音的数量差d是否为0。即如果v和c表示元音和辅音的数量，则d = v - c，当d为0时，此条件满足。对于`(vowels * consonants) % k == 0`条件的检测，利用了前面通过数学分解得到的x值。这里的检查转换为检测v % x的值，其中x是使得v * v % k == 0的最小值。每次在遍历字符串时，都会更新当前的v和c值，并计算当前的d和v % x值，并在哈希表中查找是否存在之前的前缀和符合这些条件，从而判断以当前位置结尾的子字符串是否满足条件。

在这个解法中，哈希表`m`用来存储每个可能的差值d和对x取模后的v值对应的前缀出现次数。这样的双层结构允许我们快速地查找到所有前缀，它们的元音和辅音数量差和当前差相同，并且它们的元音数量对x取模的结果也与当前相同。这意味着从这些前缀点到当前点的子字符串满足`vowels == consonants`和`(vowels * consonants) % k == 0`的条件。通过统计这些符合条件的前缀数，我们可以快速计算出以当前字符结尾的所有美丽子字符串的数量，从而高效地解决问题。