LeetCode 题解工作台
由单个字符重复的最长子字符串
给你一个下标从 0 开始的字符串 s 。另给你一个下标从 0 开始、长度为 k 的字符串 queryCharacters ，一个下标从 0 开始、长度也是 k 的整数 下标 数组 queryIndices ，这两个都用来描述 k 个查询。 第 i 个查询会将 s 中位于下标 queryIndices…
4
题型
5
代码语言
3
相关题
当前训练重点
困难 · 数组·string
答案摘要
线段树将整个区间分割为多个不连续的子区间，子区间的数量不超过 。更新某个元素的值，只需要更新 个区间，并且这些区间都包含在一个包含该元素的大区间内。区间修改时，需要使用懒标记保证效率。 - 线段树的每个节点代表一个区间；
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·string 题型思路
题目描述
给你一个下标从 0 开始的字符串 s 。另给你一个下标从 0 开始、长度为 k 的字符串 queryCharacters ，一个下标从 0 开始、长度也是 k 的整数 下标 数组 queryIndices ，这两个都用来描述 k 个查询。
第 i 个查询会将 s 中位于下标 queryIndices[i] 的字符更新为 queryCharacters[i] 。
返回一个长度为 k 的数组 lengths ，其中 lengths[i] 是在执行第 i 个查询 之后 s 中仅由 单个字符重复 组成的 最长子字符串 的 长度 。
示例 1：
输入：s = "babacc", queryCharacters = "bcb", queryIndices = [1,3,3] 输出：[3,3,4] 解释： - 第 1 次查询更新后 s = "bbbacc" 。由单个字符重复组成的最长子字符串是 "bbb" ，长度为 3 。 - 第 2 次查询更新后 s = "bbbccc" 。由单个字符重复组成的最长子字符串是 "bbb" 或 "ccc"，长度为 3 。 - 第 3 次查询更新后 s = "bbbbcc" 。由单个字符重复组成的最长子字符串是 "bbbb" ，长度为 4 。 因此，返回 [3,3,4] 。
示例 2：
输入：s = "abyzz", queryCharacters = "aa", queryIndices = [2,1] 输出：[2,3] 解释： - 第 1 次查询更新后 s = "abazz" 。由单个字符重复组成的最长子字符串是 "zz" ，长度为 2 。 - 第 2 次查询更新后 s = "aaazz" 。由单个字符重复组成的最长子字符串是 "aaa" ，长度为 3 。 因此，返回 [2,3] 。
提示：
1 <= s.length <= 105s由小写英文字母组成k == queryCharacters.length == queryIndices.length1 <= k <= 105queryCharacters由小写英文字母组成0 <= queryIndices[i] < s.length
解题思路
方法一：线段树
线段树将整个区间分割为多个不连续的子区间，子区间的数量不超过 。更新某个元素的值，只需要更新 个区间，并且这些区间都包含在一个包含该元素的大区间内。区间修改时，需要使用懒标记保证效率。
- 线段树的每个节点代表一个区间；
- 线段树具有唯一的根节点，代表的区间是整个统计范围，如 ；
- 线段树的每个叶子节点代表一个长度为 的元区间 ；
- 对于每个内部节点 ，它的左儿子是 ，右儿子是 , 其中 ；
对于本题，线段树节点维护的信息有：
- 前缀最长连续字符个数 ；
- 后缀最长连续字符个数 ；
- 区间最长连续字符个数 。
- 区间左端点 和右端点 。
时间复杂度 ，空间复杂度 。其中 是字符串 的长度。
def max(a: int, b: int) -> int:
return a if a > b else b
class Node:
__slots__ = "l", "r", "lmx", "rmx", "mx"
def __init__(self, l: int, r: int):
self.l = l
self.r = r
self.lmx = self.rmx = self.mx = 1
class SegmentTree:
__slots__ = "s", "tr"
def __init__(self, s: str):
self.s = list(s)
n = len(s)
self.tr: List[Node | None] = [None] * (n * 4)
self.build(1, 1, n)
def build(self, u: int, l: int, r: int):
self.tr[u] = Node(l, r)
if l == r:
return
mid = (l + r) // 2
self.build(u << 1, l, mid)
self.build(u << 1 | 1, mid + 1, r)
self.pushup(u)
def query(self, u: int, l: int, r: int) -> int:
if self.tr[u].l >= l and self.tr[u].r <= r:
return self.tr[u].mx
mid = (self.tr[u].l + self.tr[u].r) // 2
ans = 0
if r <= mid:
ans = self.query(u << 1, l, r)
if l > mid:
ans = max(ans, self.query(u << 1 | 1, l, r))
return ans
def modify(self, u: int, x: int, v: str):
if self.tr[u].l == self.tr[u].r:
self.s[x - 1] = v
return
mid = (self.tr[u].l + self.tr[u].r) // 2
if x <= mid:
self.modify(u << 1, x, v)
else:
self.modify(u << 1 | 1, x, v)
self.pushup(u)
def pushup(self, u: int):
root, left, right = self.tr[u], self.tr[u << 1], self.tr[u << 1 | 1]
root.lmx = left.lmx
root.rmx = right.rmx
root.mx = max(left.mx, right.mx)
a, b = left.r - left.l + 1, right.r - right.l + 1
if self.s[left.r - 1] == self.s[right.l - 1]:
if left.lmx == a:
root.lmx += right.lmx
if right.rmx == b:
root.rmx += left.rmx
root.mx = max(root.mx, left.rmx + right.lmx)
class Solution:
def longestRepeating(
self, s: str, queryCharacters: str, queryIndices: List[int]
) -> List[int]:
tree = SegmentTree(s)
ans = []
for x, v in zip(queryIndices, queryCharacters):
tree.modify(1, x + 1, v)
ans.append(tree.query(1, 1, len(s)))
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
They mention fast point updates and repeated answers after each edit, which strongly hints that rescanning is the trap.
- question_mark
They ask how to combine two segments, which means they want the exact merge state instead of a vague tree description.
- question_mark
They focus on boundary behavior, especially when one updated character joins two equal runs across the middle.
常见陷阱
外企场景- error
Storing only the best run per segment is not enough; you also need prefix and suffix run lengths plus boundary characters to merge correctly.
- error
Forgetting the cross-boundary merge causes wrong answers when an update connects two same-character blocks into a longer run.
- error
Treating this like a frequency problem is incorrect because the answer depends on contiguous runs, not total character counts.
进阶变体
外企场景- arrow_right_alt
Return the longest repeating run only after all updates, where a simple final scan would work but misses the online requirement of this problem.
- arrow_right_alt
Support range assignment updates instead of single-index updates, which usually needs lazy propagation on top of the same run metadata.
- arrow_right_alt
Track a different segment metric such as longest alternating substring, where the merge state changes because equality is no longer the winning condition.