千问 LeetCode 2949. 统计美丽子字符串 II Java实现

这道题的核心在于将“美丽子字符串”的两个条件转化为可以通过前缀和与哈希表快速求解的形式。题目解析一个子字符串是“美丽”的需要满足1. 元音字母数量 辅音字母数量。2. (元音数量 × 辅音数量) % k 0。核心思路1. 条件转化* 设子字符串长度为 L由条件1可知元音和辅音数量均为 L/2。* 代入条件2得到 (L/2 * L/2) % k 0即 (L/2)² % k 0。* 这意味着我们需要找到一个最小的周期长度 mod使得子字符串的长度 L 必须是 mod 的倍数。通过对 4*k 进行质因数分解我们可以求出这个最小的 mod具体求法见代码中的 getMod 方法。2. 前缀和与哈希表* 遍历字符串遇到元音字母前缀和 sum 1遇到辅音字母 sum - 1。* 如果两个位置 i 和 j 的前缀和相等sum[i] sum[j]说明从 i1 到 j 的这段子字符串中元音和辅音数量相等满足条件1。* 同时我们需要保证这段子字符串的长度 (j - i) 是 mod 的倍数即 j % mod i % mod满足条件2。* 因此我们使用哈希表来记录状态键为 (前缀和, 下标 % mod)值为该状态出现的次数。Java 代码实现import java.util.HashMap;import java.util.Map;class Solution {public long beautifulSubstrings(String s, int k) {// 1. 计算满足 (L/2)^2 % k 0 的最小周期长度 modint mod getMod(k);long ans 0;int sum 0; // 前缀和元音1辅音-1// 2. 哈希表记录状态 (前缀和, 下标 % mod) 出现的次数// 初始状态前缀和为0下标为-1对应虚拟下标(-1) % mod 处理为 mod - 1MapString, Integer map new HashMap();map.put((mod - 1) , 0, 1);for (int i 0; i s.length(); i) {char c s.charAt(i);// 遇到元音1辅音-1if (c a || c e || c i || c o || c u) {sum;} else {sum--;}// 当前状态的下标余数int remainder i % mod;String key remainder , sum;// 如果之前出现过相同的状态说明中间这段子字符串满足条件ans map.getOrDefault(key, 0);// 更新当前状态的出现次数map.put(key, map.getOrDefault(key, 0) 1);}return ans;}// 对 4*k 进行质因数分解求出满足 x^2 % (4*k) 0 的最小 xprivate int getMod(int k) {int m 4 * k;int mod 1;for (int i 2; i * i m; i) {if (m % i 0) {int cnt 0;while (m % i 0) {m / i;cnt;}// 如果质因数的次数是奇数需要多乘一个 i 保证平方后能被整除mod * Math.pow(i, (cnt 1) / 2);}}// 处理剩下的最大质因数if (m 1) {mod * m;}return mod;}}复杂度分析* 时间复杂度O(n sqrt(k))。其中 n 是字符串长度遍历字符串需要 O(n)计算 mod 的质因数分解需要 O(sqrt(k))。* 空间复杂度O(n)。哈希表在最坏情况下需要存储 n 个不同的前缀和状态。