leetcode
leetcode 1951 ~ 2000
由单个字符重复的最长子字符串

由单个字符重复的最长子字符串

难度:

标签:

题目描述

代码结果

运行时间: 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划分,这个过程中是如何确保每个子字符串都仅由相同字符组成的?
在Python中,`itertools.groupby`函数可以将连续的相同元素分组。传给`groupby`的参数是字符串`s`,它会根据每个字符的相等性来分组。每次迭代返回一个键和一个迭代器,键是组中的字符,迭代器包含该字符的连续重复序列。因此,这种方式自然地确保了每个通过`groupby`生成的子序列都是由完全相同的字符构成。
🦆
在执行split函数时,如果index位置的字符与前一个字符相同,为何还需要进行分割?
在`s`中的特定`index`处执行`split`函数的目的是为了正确地处理字符的更新,即使该字符与原位置字符相同。分割主要是因为更新操作可能影响已有区间的结构。例如,如果在`index`处的字符被更新(即使更新后字符相同),我们可能需要重新划分边界来确保后续的`union`操作可以正确地合并新的相同字符区间。这样的设计确保了数据结构的一致性和查询的准确性。
🦆
题解中的union函数是如何判断两个相邻区间是否可以合并的?具体是基于哪些条件来决定合并操作?
在`union`函数中,合并两个相邻区间的决策基于两个主要条件:1) 这两个区间是否是相邻的;2) 区间的边界字符是否相同。首先,函数检查当前区间和前一个区间的位置,如果它们是连续的(即一个区间的结束位置与另一个区间的开始位置相邻),然后检查这两个区间的字符是否相同。如果这两个条件都满足,那么这两个区间可以合并成一个更大的区间。这样的合并有助于维护和更新最长连续相同字符子串的长度。
🦆
在更新SortedDict和SortedList时,题解如何处理已经存在的区间长度删除和新区间长度添加的操作?
在更新`SortedDict`和`SortedList`时,首先要做的是从`SortedList`中删除旧的区间长度。这是通过直接调用`remove`方法完成的,该方法根据原有的区间长度删除相关的条目。紧接着,当新的区间长度形成(无论是通过分割还是合并操作),新的长度将被添加到`SortedList`中,使用`add`方法。这种方式确保`SortedList`始终保持最新的区间长度信息,从而可以快速返回最大的区间长度。

相关问题