共计 3572 个字符，预计需要花费 9 分钟才能阅读完成。
题目形容
这是 LeetCode 上的 2213. 由单个字符反复的最长子字符串 ，难度为 艰难。
Tag :「区间求和」、「线段树」
给你一个下标从 $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 <= 10^5$
s由小写英文字母组成- $k == queryCharacters.length == queryIndices.length$
- $1 <= k <= 10^5$
queryCharacters由小写英文字母组成- $0 <= queryIndices[i] < s.length$
线段树
这是一道经典的线段树应用题。
依据题意，波及的操作“仿佛”是「单点批改」和「区间查问」，那么依据 (题解) 307. 区域和检索 – 数组可批改 的总结，咱们应该应用的是「树状数组」吗？
其实并不是（或者说不能间接是），起因在于咱们查问的是「批改过后 s 中雷同字符间断段的最大长度」，而当咱们进行所谓的「单点批改」时，会导致本来的间断段被毁坏，或者造成新的间断段。也就是此处的批改对于后果而言，并不是单点的。
应用线段树求解，咱们惟一须要思考的是：在 Node 中保护些什么信息？
对于线段树的节点信息设计，通常会蕴含根本的左右端点 l、r 以及查问目标值 val，而后再思考保护 val 还须要一些什么辅助信息。
对于本题，咱们还须要额定保护 prefix 和 suffix，别离代表「以后区间 $[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(n)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.2213 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布
