题目描述
这是 LeetCode 上的 2213. 由单个字符重复的最长子字符串 ，难度为 困难。
Tag : 「区间求和」、「线段树」
给你一个下标从 00 开始的字符串 s 。另给你一个下标从 00 开始、长度为 kk 的字符串 queryCharacters，一个下标从 00 开始、长度也是 kk 的整数 下标 数组 queryIndices，这两个都用来描述 kk 个查询。
第 ii 个查询会将 s 中位于下标 queryIndices[i]queryIndices[i] 的字符更新为 queryCharacters[i]queryCharacters[i]。
返回一个长度为 kk 的数组 lengths，其中 lengths[i]lengths[i] 是在执行第 ii 个查询之后 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 <= 10^51<=s.length<=105
s由小写英文字母组成- k == queryCharacters.length == queryIndices.lengthk==queryCharacters.length==queryIndices.length
- 1 <= k <= 10^51<=k<=105
queryCharacters由小写英文字母组成- 0 <= queryIndices[i] < s.length0<=queryIndices[i]<s.length
线段树
这是一道经典的线段树应用题。
根据题意，涉及的操作 “似乎” 是「单点修改」和「区间查询」，那么根据 (题解) 307. 区域和检索 - 数组可修改 的总结，我们应该使用的是「树状数组」吗？
其实并不是（或者说不能直接是），原因在于我们查询的是「修改过后 s 中相同字符连续段的最大长度」，而当我们进行所谓的「单点修改」时，会导致原本的连续段被破坏，或者形成新的连续段。也就是此处的修改对于结果而言，并不是单点的。
使用线段树求解，我们唯一需要考虑的是：在 Node 中维护些什么信息？
对于线段树的节点信息设计，通常会包含基本的左右端点 l、r 以及查询目标值 val ，然后再考虑维护 val 还需要一些什么辅助信息。
对于本题，我们还需要额外维护 prefix 和 suffix，分别代表「当前区间 [l, r][l,r] 内前缀相同字符连续段的最大长度」和「当前区间 [l, r][l,r] 内后缀相同字符连续段的最大长度」。
然后考虑每次修改，如何使用子节点信息更新父节点（pushup 操作）：
- 对于一般性的合并（当前节点的两个子节点的衔接点不是相同字符）而言：
tr[u].prefix = tr[u << 1].prefix：当前父节点（区间）的前缀最大长度等于左子节点（区间）的前缀最大长度；tr[u].suffix = tr[u << 1 | 1].suffix：当前父节点（区间）的后缀最大长度等于右子节点（区间）的后缀最大长度；tr[u].val = max(left.val, right.val)：当前父节点（区间）的最大长度为两子节点（区间）的最大长度。
- 对于非一般性的合并（当前节点的两个子节点的衔接点为相同字符）：
tr[u].val = max(tr[u].val, left.suffix + right.prefix)：首先可以确定的是「左区间的后缀」和「右区间的前缀」可以拼接在一起，因此可以使用拼接长度来尝试更新当前节点的最大值；tr[u].suffix = bLen + left.suffix：其中bLen为右节点（区间）的长度。当且仅当右节点（区间）整一段都是相同字符时（即满足right.prefix = right.suffix = bLen），可以使用bLen + left.suffix来更新tr[u].suffix；tr[u].prefix = aLen + right.prefix：其中aLen为左节点（区间）的长度。当且仅当左节点（区间）整一段都是相同字符时（即满足left.prefix = left.prefix = aLen），可以使用aLen + right.prefix来更新tr[u].prefix。
代码：
class Solution { class Node { int l, r, prefix, suffix, val; Node(int _l, int _r) { l = _l; r = _r; prefix = suffix = val = 1; } } char[] cs; Node[] tr; void build(int u, int l, int r) { tr[u] = new Node(l, r); if (l == r) return ; int mid = l + r >> 1; build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r); } void update(int u, int x, char c) { if (tr[u].l == x && tr[u].r == x) { cs[x - 1] = c; return ; } int mid = tr[u].l + tr[u].r >> 1; if (x <= mid) update(u << 1, x, c); else update(u << 1 | 1, x, c); pushup(u); } int query(int u, int l, int r) { if (l <= tr[u].l && tr[u].r <= r) return tr[u].val; int ans = 0; int mid = tr[u].l + tr[u].r >> 1; if (l <= mid) ans = query(u << 1, l, r); if (r > mid) ans = Math.max(ans, query(u << 1 | 1, l, r)); return ans; } void pushup(int u) { Node left = tr[u << 1], right = tr[u << 1 | 1]; int aLen = left.r - left.l + 1, bLen = right.r - right.l + 1; char ac = cs[left.r - 1], bc = cs[right.l - 1]; tr[u].prefix = left.prefix; tr[u].suffix = right.suffix; tr[u].val = Math.max(left.val, right.val); if (ac == bc) { if (left.prefix == aLen) tr[u].prefix = aLen + right.prefix; if (right.prefix == bLen) tr[u].suffix = bLen + left.suffix; tr[u].val = Math.max(tr[u].val, left.suffix + right.prefix); } } public int[] longestRepeating(String s, String queryCharacters, int[] queryIndices) { cs = s.toCharArray(); int n = cs.length, m = queryCharacters.length(); tr = new Node[n * 4]; build(1, 1, n); for (int i = 0; i < n; i++) update(1, i + 1, cs[i]); int[] ans = new int[m]; for (int i = 0; i < m; i++) { update(1, queryIndices[i] + 1, queryCharacters.charAt(i)); ans[i] = query(1, 1, n); } return ans; } } 复制代码
- 时间复杂度：O(m * \log{n})O(m∗logn)
- 空间复杂度：O(n)O(n)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.2213 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
