统计美丽子字符串 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 ofvowelsandconsonantsis divisible byk.
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 * 1041 <= k <= 1000sconsists of only English lowercase letters.
代码结果
运行时间: 160 ms, 内存: 19.0 MB
/*
* 思路：
* 1. 使用Java Stream API处理字符串。
* 2. 遍历所有子字符串，计算元音和辅音的数量。
* 3. 检查元音数量等于辅音数量，并且它们的乘积能被k整除。
* 4. 返回满足条件的子字符串数量。
*/
import java.util.stream.IntStream;
public class Solution {
public int countBeautifulSubstrings(String s, int k) {
int n = s.length();
String vowels = "aeiou";
return (int) IntStream.range(0, n).flatMap(i -> IntStream.range(i + 1, n + 1).mapToObj(j -> s.substring(i, j)))
.filter(sub -> {
long vowelCount = sub.chars().filter(ch -> vowels.indexOf(ch) != -1).count();
long consonantCount = sub.length() - vowelCount;
return vowelCount == consonantCount && (vowelCount * consonantCount) % k == 0;
}).count();
}
}解释
方法:
这个题解利用了数学和哈希表的方法来统计美丽子字符串。首先，它通过分解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)
代码细节讲解
🦆
为什么在题解中需要分解整数k，并找到一个最小的x满足特定条件？这个过程的数学依据是什么？
▷🦆
题解中提到的两个条件`vowels == consonants`和`(vowels * consonants) % k == 0`，在算法实现中是如何被检测和处理的？
▷🦆
哈希表在这个解法中起了什么作用？特别是`m[d][v % x]`这样的双层结构是如何帮助统计符合条件的子字符串的？
▷