leetcode
leetcode 1901 ~ 1950
每个数字的频率都相同的独特子字符串的数量

每个数字的频率都相同的独特子字符串的数量

难度:

标签:

题目描述

代码结果

运行时间: 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)

代码细节讲解

🦆
在构建累积频率数组时,为什么选择使用一个二维数组,每行代表一个数字字符,并且列数为字符串长度加一?
使用二维数组的目的是为了快速查询任何子字符串中的每个数字字符的出现次数。每一行代表一个数字(0-9),确保可以分别处理每个数字的出现频率。列数为字符串长度加一(n+1),是因为累积频率数组的第一列用于初始化,设为0,表示字符串开头前没有任何字符。这样可以方便地通过区间差计算出任何子字符串中每个数字的频率,即通过结束位置的频率减去开始位置之前的频率获得。
🦆
累积频率数组中,每个位置更新的方式是什么?具体来说,当处理到字符串的某个字符时,该如何更新累积频率数组中的值?
累积频率数组的更新方式是:对于字符串中的每个字符,首先将该字符对应的ASCII值转换为对应的数字索引(例如,字符'0'到'9'转换为索引0到9)。然后,对于每个数字0-9,更新它们在累积频率数组中的当前位置的值。具体地,如果当前字符对应的数字是d,则在d对应的行的当前列位置上的值,等于该行前一列的值加1;其他行的当前列的值,等于它们各自前一列的值。这样,每行的每列值都保持了从字符串开头到当前位置该数字的总出现次数。
🦆
为什么需要在最终结果中将单字符子字符串的数量单独计算并加到独特子字符串的数量中?
单字符子字符串需要单独计算,因为这些子字符串自然满足所有字符频率相同的条件(只有一个字符)。直接通过累积频率数组的最后一列判断每个数字是否在整个字符串中至少出现一次,可以快速统计有多少种单字符子字符串。将这个数量加到其他满足条件的独特子字符串数量中,是因为这些单字符子字符串也是有效的符合条件的子字符串,应被计入总数。
🦆
检查子字符串时,你是如何确定所有数字的出现频率相同?具体的逻辑是什么?
在检查子字符串是否所有数字的出现频率相同时,逻辑是:首先计算子字符串中每个数字的出现次数,这可以通过累积频率数组快速完成(每个数字的出现次数等于该数字在子字符串结束位置加一的累积频率减去在子字符串开始位置的累积频率)。然后,遍历这些频率,比较第一个非零频率(即子字符串中至少出现一次的数字的频率)与其他非零频率是否相同。如果找到任何不同的频率,则当前子字符串不满足条件;如果所有非零频率相同,则该子字符串满足条件。

相关问题