由单个字符重复的最长子字符串
难度:
标签:
题目描述
代码结果
运行时间: 3867 ms, 内存: 36.7 MB
/*
* Solution for the given problem using Java Streams
*
* We process each query one by one and use streams to update the character and find the longest repeating substring.
*/
import java.util.Arrays;
import java.util.stream.IntStream;
public class SolutionStream {
public int[] longestRepeating(String s, String queryCharacters, int[] queryIndices) {
StringBuilder sb = new StringBuilder(s);
return IntStream.range(0, queryCharacters.length())
.map(i -> {
sb.setCharAt(queryIndices[i], queryCharacters.charAt(i));
return findLongestRepeatingSubstring(sb.toString());
})
.toArray();
}
private int findLongestRepeatingSubstring(String s) {
int[] maxLength = {1};
int[] currentLength = {1};
IntStream.range(1, s.length()).forEach(i -> {
if (s.charAt(i) == s.charAt(i - 1)) {
currentLength[0]++;
maxLength[0] = Math.max(maxLength[0], currentLength[0]);
} else {
currentLength[0] = 1;
}
});
return maxLength[0];
}
}
解释
方法:
题解使用了SortedDict和SortedList来维护子字符串的信息。首先,初始化过程中,通过groupby将字符串s划分为由相同字符组成的多个子字符串,并存储这些子字符串的起始和结束位置到SortedDict中,同时将子字符串的长度存入SortedList中。对于每次查询,先检查新字符是否与原字符相同,若相同则直接返回当前最长重复子字符串长度;若不同,则更新字符,并分割和合并相关区间以维护正确的子字符串信息。分割操作确保每次查询只影响一个很小的区间,而合并操作尝试将相邻的由相同字符组成的区间合并起来。通过这种方式,每次查询后都能快速获取最长重复子字符串的长度。
时间复杂度:
O(n + k log n)
空间复杂度:
O(n)
代码细节讲解
🦆
题解中提到初始化时使用groupby将字符串s划分,这个过程中是如何确保每个子字符串都仅由相同字符组成的?
▷🦆
在执行split函数时,如果index位置的字符与前一个字符相同,为何还需要进行分割?
▷🦆
题解中的union函数是如何判断两个相邻区间是否可以合并的?具体是基于哪些条件来决定合并操作?
▷🦆
在更新SortedDict和SortedList时,题解如何处理已经存在的区间长度删除和新区间长度添加的操作?
▷