每个数字的频率都相同的独特子字符串的数量
难度:
标签:
题目描述
代码结果
运行时间: 1596 ms, 内存: 16.9 MB
/**
* 题目编号: 2168
* 题目: 每个数字的频率都相同的独特子字符串的数量
*
* 题目思路:
* 1. 使用双指针方法找到所有可能的子字符串。
* 2. 对于每个子字符串,检查其每个字符的频率是否相同。
* 3. 使用HashSet存储独特的满足条件的子字符串。
*/
import java.util.HashSet;
import java.util.stream.IntStream;
public class UniqueSubstringsStream {
public static int countUniqueSubstrings(String s) {
HashSet<String> uniqueSubstrings = new HashSet<>();
int n = s.length();
IntStream.range(0, n).forEach(i -> {
int[] freq = new int[10]; // 假设输入的字符串只包含数字0-9
IntStream.range(i, n).forEach(j -> {
freq[s.charAt(j) - '0']++;
if (areFrequenciesEqual(freq)) {
uniqueSubstrings.add(s.substring(i, j + 1));
}
});
});
return uniqueSubstrings.size();
}
private static boolean areFrequenciesEqual(int[] freq) {
int count = IntStream.of(freq).filter(f -> f > 0).findFirst().orElse(0);
return IntStream.of(freq).filter(f -> f > 0).allMatch(f -> f == count);
}
public static void main(String[] args) {
String s = "122333";
System.out.println(countUniqueSubstrings(s)); // 示例输出
}
}
解释
方法:
题解首先采用预处理方式建立累积频率数组(accus),用于快速查询任何子字符串中每个数字字符的出现次数。这个二维数组的每一行代表一个数字(0-9),每一列的值代表从字符串开始到当前位置该数字的出现总次数。之后,解法通过遍历所有可能的子字符串,检查每个子字符串内所有数字的出现频率是否相同。如果一个子字符串中所有出现的数字的频率相同,则将其添加到集合中以避免重复计数。最终,函数返回独特满足条件的子字符串数量。
时间复杂度:
O(n^2)
空间复杂度:
O(n^2)
代码细节讲解
🦆
在构建累积频率数组时,为什么选择使用一个二维数组,每行代表一个数字字符,并且列数为字符串长度加一?
▷🦆
累积频率数组中,每个位置更新的方式是什么?具体来说,当处理到字符串的某个字符时,该如何更新累积频率数组中的值?
▷🦆
为什么需要在最终结果中将单字符子字符串的数量单独计算并加到独特子字符串的数量中?
▷🦆
检查子字符串时,你是如何确定所有数字的出现频率相同?具体的逻辑是什么?
▷