Readme

2949.Count-Beautiful-Substrings-II

对于求substring的问题，我们很容想到用前缀和之差来解决。显然，对于以i结尾的substring，我们想要找满足条件的起始位置j，需要满足两个条件：

1. [j+1:i]内的元音辅音个数相等 <-> [0:j]的元音辅音个数之差必须等于[0:i]的元音辅音个数之差。
2. [j+1:i]内的元音辅音个数乘积能被k整除 <-> [(i-j)/2]^2 % k ==0 <-> [(i-j)]^2 % 4k ==0

对于第一个条件，我们只要根据[0:i]的元音辅音个数之差（假设为d），在hash表中查找之前有多少个前缀串的元音辅音个数之差也是d。

对于第二个条件，理论上只要i与j关于sqrt(4k)同余，那么(i-j)就能被sqrt(4k)整除，也就是说(i-j)^2能被4k整除。但是sqrt(4k)可能不是一个整数。所以我们需要将k分解质因数，对于出现奇数次的质因子，显然我们需要再补一个该质因子以便k能被开方。我们将这样“松弛”后的k的开方结果记做m，那么我们只要i与j关于2m同余。就保证[(i-j)]^2能被4k整除。

于是本题的思路就是建立包含两个key的hash，来记录每个前缀的两个信息：元音辅音的个数之差，前缀长度关于2m的余数。对于任意的位置i，如果在hash表里能找到两个key都相同的位置j，那么[j+1:i]就是符合要求的substring。