统计重复个数
难度:
标签:
题目描述
定义 str = [s, n] 表示 str 由 n 个字符串 s 连接构成。
- 例如，
str == ["abc", 3] =="abcabcabc"。
如果可以从 s2 中删除某些字符使其变为 s1，则称字符串 s1 可以从字符串 s2 获得。
- 例如，根据定义，
s1 = "abc"可以从s2 = "abdbec"获得，仅需要删除加粗且用斜体标识的字符。
现在给你两个字符串 s1 和 s2 和两个整数 n1 和 n2 。由此构造得到两个字符串，其中 str1 = [s1, n1]、str2 = [s2, n2] 。
请你找出一个最大整数 m ，以满足 str = [str2, m] 可以从 str1 获得。
示例 1：
输入：s1 = "acb", n1 = 4, s2 = "ab", n2 = 2 输出：2
示例 2：
输入：s1 = "acb", n1 = 1, s2 = "acb", n2 = 1 输出：1
提示：
1 <= s1.length, s2.length <= 100s1和s2由小写英文字母组成1 <= n1, n2 <= 106
代码结果
运行时间: 27 ms, 内存: 16.2 MB
/*
* 思路：
* 1. 使用Java Stream构建str1和str2。
* 2. 构建一个辅助函数check(s1, s2)来判断s2是否是s1的子序列。
* 3. 使用stream处理字符串的构建和重复的逻辑。
*/
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class Solution {
// 辅助函数：判断s2是否是s1的子序列
public boolean check(String s1, String s2) {
int j = 0;
for (int i = 0; i < s1.length() && j < s2.length(); i++) {
if (s1.charAt(i) == s2.charAt(j)) {
j++;
}
}
return j == s2.length();
}
public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
String longStr1 = IntStream.range(0, n1).mapToObj(i -> s1).collect(Collectors.joining());
String longStr2 = IntStream.range(0, n2).mapToObj(i -> s2).collect(Collectors.joining());
int m = 0;
while (check(longStr1, longStr2)) {
m++;
longStr2 += s2;
}
return m;
}
}
解释
方法:
这个题解使用哈希表来记录在 s1 的每个完整循环中，s2 完整出现的次数以及当前匹配到的 s2 的下标。当再次出现相同的 s2 下标时，说明出现了循环节，可以直接计算出在剩余的 s1 循环中，s2 完整出现的次数，从而避免了后续的循环计算。最后将 s2 出现的总次数除以 n2，得到 s2 在 s1 中重复出现的最大次数。
时间复杂度:
O(mn)
空间复杂度:
O(n)
代码细节讲解
🦆
在解决这个问题时，为什么选择使用哈希表来记录每个s2下标对应的s1的循环次数和s2的出现次数？
▷🦆
题解中提到当发现循环节时可以直接计算出剩余的s2出现次数，这种方法的正确性是如何保证的？
▷🦆
在题解的实现中，如何处理s2的下标在哈希表中已经存在的情况？请详细解释这一步的逻辑。
▷🦆
在哈希表中记录的信息包括s2的下标、s1的循环次数和s2的出现次数，这些信息是如何帮助我们检测到循环节的？
▷