class Solution {
public:
vector<int> longestRepeating(string s, string queryCharacters, vector<int>& queryIndices) {
}
};
2213. 由单个字符重复的最长子字符串
给你一个下标从 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原站题解
golang 解法, 执行用时: 188 ms, 内存消耗: 46.7 MB, 提交时间: 2023-10-10 23:07:41
var s []byte
type seg []struct{ l, r, pre, suf, max int }
func (t seg) maintain(o int) {
lo, ro := t[o<<1], t[o<<1|1]
t[o].pre = lo.pre
t[o].suf = ro.suf
t[o].max = max(lo.max, ro.max)
if s[lo.r-1] == s[lo.r] { // 中间字符相同，可以合并
if lo.suf == lo.r-lo.l+1 {
t[o].pre += ro.pre
}
if ro.pre == ro.r-ro.l+1 {
t[o].suf += lo.suf
}
t[o].max = max(t[o].max, lo.suf+ro.pre)
}
}
func (t seg) build(o, l, r int) {
t[o].l, t[o].r = l, r
if l == r {
t[o].pre = 1
t[o].suf = 1
t[o].max = 1
return
}
m := (l + r) >> 1
t.build(o<<1, l, m)
t.build(o<<1|1, m+1, r)
t.maintain(o)
}
func (t seg) update(o, i int) {
if t[o].l == t[o].r {
return
}
m := (t[o].l + t[o].r) >> 1
if i <= m {
t.update(o<<1, i)
} else {
t.update(o<<1|1, i)
}
t.maintain(o)
}
func longestRepeating(S, queryCharacters string, queryIndices []int) []int {
s = []byte(S)
n := len(s)
t := make(seg, n*4)
t.build(1, 1, n)
ans := make([]int, len(queryIndices))
for i, index := range queryIndices {
s[index] = queryCharacters[i]
t.update(1, index+1)
ans[i] = t[1].max
}
return ans
}
func max(a, b int) int { if b > a { return b }; return a }
cpp 解法, 执行用时: 392 ms, 内存消耗: 85.5 MB, 提交时间: 2023-10-10 23:07:28
class Solution {
string s;
vector<int> pre, suf, max;
void maintain(int o, int l, int r) {
pre[o] = pre[o << 1];
suf[o] = suf[o << 1 | 1];
max[o] = std::max(max[o << 1], max[o << 1 | 1]);
int m = (l + r) >> 1;
if (s[m - 1] == s[m]) { // 中间字符相同，可以合并
if (suf[o << 1] == m - l + 1) pre[o] += pre[o << 1 | 1];
if (pre[o << 1 | 1] == r - m) suf[o] += suf[o << 1];
max[o] = std::max(max[o], suf[o << 1] + pre[o << 1 | 1]);
}
}
void build(int o, int l, int r) {
if (l == r) {
pre[o] = suf[o] = max[o] = 1;
return;
}
int m = (l + r) / 2;
build(o << 1, l, m);
build(o << 1 | 1, m + 1, r);
maintain(o, l, r);
}
void update(int o, int l, int r, int i) {
if (l == r) return;
int m = (l + r) / 2;
if (i <= m) update(o << 1, l, m, i);
else update(o << 1 | 1, m + 1, r, i);
maintain(o, l, r);
}
public:
vector<int> longestRepeating(string &s, string &queryCharacters, vector<int> &queryIndices) {
this->s = s;
int n = s.length(), m = queryIndices.size();
pre.resize(n << 2);
suf.resize(n << 2);
max.resize(n << 2);
build(1, 1, n);
vector<int> ans(m);
for (int i = 0; i < m; ++i) {
this->s[queryIndices[i]] = queryCharacters[i];
update(1, 1, n, queryIndices[i] + 1);
ans[i] = max[1];
}
return ans;
}
};
java 解法, 执行用时: 112 ms, 内存消耗: 58.5 MB, 提交时间: 2023-10-10 23:07:13
class Solution {
char[] s;
int[] pre, suf, max;
void maintain(int o, int l, int r) {
pre[o] = pre[o << 1];
suf[o] = suf[o << 1 | 1];
max[o] = Math.max(max[o << 1], max[o << 1 | 1]);
var m = (l + r) >> 1;
if (s[m - 1] == s[m]) { // 中间字符相同，可以合并
if (suf[o << 1] == m - l + 1) pre[o] += pre[o << 1 | 1];
if (pre[o << 1 | 1] == r - m) suf[o] += suf[o << 1];
max[o] = Math.max(max[o], suf[o << 1] + pre[o << 1 | 1]);
}
}
void build(int o, int l, int r) {
if (l == r) {
pre[o] = suf[o] = max[o] = 1;
return;
}
var m = (l + r) / 2;
build(o << 1, l, m);
build(o << 1 | 1, m + 1, r);
maintain(o, l, r);
}
void update(int o, int l, int r, int i) {
if (l == r) return;
var m = (l + r) / 2;
if (i <= m) update(o << 1, l, m, i);
else update(o << 1 | 1, m + 1, r, i);
maintain(o, l, r);
}
public int[] longestRepeating(String s, String queryCharacters, int[] queryIndices) {
this.s = s.toCharArray();
int n = this.s.length, m = queryIndices.length;
pre = new int[n << 2];
suf = new int[n << 2];
max = new int[n << 2];
build(1, 1, n);
var ans = new int[m];
for (var i = 0; i < m; ++i) {
this.s[queryIndices[i]] = queryCharacters.charAt(i);
update(1, 1, n, queryIndices[i] + 1);
ans[i] = max[1];
}
return ans;
}
}
python3 解法, 执行用时: 6136 ms, 内存消耗: 79.3 MB, 提交时间: 2023-10-10 23:07:00
class Solution:
def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:
s = list(s)
n = len(s)
pre = [0] * (4 * n)
suf = [0] * (4 * n)
mx = [0] * (4 * n)
def maintain(o: int, l: int, r: int) -> None:
pre[o] = pre[o * 2]
suf[o] = suf[o * 2 + 1]
mx[o] = max(mx[o * 2], mx[o * 2 + 1])
m = (l + r) // 2
if s[m - 1] == s[m]: # 中间字符相同，可以合并
if suf[o * 2] == m - l + 1:
pre[o] += pre[o * 2 + 1]
if pre[o * 2 + 1] == r - m:
suf[o] += suf[o * 2]
mx[o] = max(mx[o], suf[o * 2] + pre[o * 2 + 1])
def build(o: int, l: int, r: int) -> None:
if l == r:
pre[o] = suf[o] = mx[o] = 1
return
m = (l + r) // 2
build(o * 2, l, m)
build(o * 2 + 1, m + 1, r)
maintain(o, l, r)
def update(o: int, l: int, r: int, i: int) -> None:
if l == r: return
m = (l + r) // 2
if i <= m:
update(o * 2, l, m, i)
else:
update(o * 2 + 1, m + 1, r, i)
maintain(o, l, r)
build(1, 1, n)
ans = []
for c, i in zip(queryCharacters, queryIndices):
s[i] = c
update(1, 1, n, i + 1)
ans.append(mx[1])
return ans