| comments | difficulty | edit_url | rating | source | tags | ||||
|---|---|---|---|---|---|---|---|---|---|
true |
Hard |
2628 |
Weekly Contest 285 Q4 |
|
You are given a 0-indexed string s. You are also given a 0-indexed string queryCharacters of length k and a 0-indexed array of integer indices queryIndices of length k, both of which are used to describe k queries.
The ith query updates the character in s at index queryIndices[i] to the character queryCharacters[i].
Return an array lengths of length k where lengths[i] is the length of the longest substring of s consisting of only one repeating character after the ith query is performed.
Example 1:
Input: s = "babacc", queryCharacters = "bcb", queryIndices = [1,3,3] Output: [3,3,4] Explanation: - 1st query updates s = "bbbacc". The longest substring consisting of one repeating character is "bbb" with length 3. - 2nd query updates s = "bbbccc". The longest substring consisting of one repeating character can be "bbb" or "ccc" with length 3. - 3rd query updates s = "bbbbcc". The longest substring consisting of one repeating character is "bbbb" with length 4. Thus, we return [3,3,4].
Example 2:
Input: s = "abyzz", queryCharacters = "aa", queryIndices = [2,1] Output: [2,3] Explanation: - 1st query updates s = "abazz". The longest substring consisting of one repeating character is "zz" with length 2. - 2nd query updates s = "aaazz". The longest substring consisting of one repeating character is "aaa" with length 3. Thus, we return [2,3].
Constraints:
1 <= s.length <= 105sconsists of lowercase English letters.k == queryCharacters.length == queryIndices.length1 <= k <= 105queryCharactersconsists of lowercase English letters.0 <= queryIndices[i] < s.length
The segment tree divides the entire interval into multiple non-continuous sub-intervals, and the number of sub-intervals does not exceed
- Each node of the segment tree represents an interval;
- The segment tree has a unique root node, which represents the entire statistical range, such as
$[1, n]$ ; - Each leaf node of the segment tree represents an elementary interval of length
$1$ ,$[x, x]$ ; - For each internal node
$[l, r]$ , its left child is$[l, mid]$ , and the right child is$[mid + 1, r]$ , where$mid = \frac{l + r}{2}$ ;
For this problem, the information maintained by the segment tree node includes:
- The number of longest consecutive characters in the prefix,
$lmx$ ; - The number of longest consecutive characters in the suffix,
$rmx$ ; - The number of longest consecutive characters in the interval,
$mx$ . - The left endpoint
$l$ and the right endpoint$r$ of the interval.
The time complexity is
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 ansclass Node {
int l, r;
int lmx, rmx, mx;
Node(int l, int r) {
this.l = l;
this.r = r;
lmx = rmx = mx = 1;
}
}
class SegmentTree {
private char[] s;
private Node[] tr;
public SegmentTree(char[] s) {
int n = s.length;
this.s = s;
tr = new Node[n << 2];
build(1, 1, n);
}
public 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);
pushup(u);
}
public void modify(int u, int x, char v) {
if (tr[u].l == x && tr[u].r == x) {
s[x - 1] = v;
return;
}
int mid = (tr[u].l + tr[u].r) >> 1;
if (x <= mid) {
modify(u << 1, x, v);
} else {
modify(u << 1 | 1, x, v);
}
pushup(u);
}
public int query(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) {
return tr[u].mx;
}
int mid = (tr[u].l + tr[u].r) >> 1;
int ans = 0;
if (r <= mid) {
ans = query(u << 1, l, r);
}
if (l > mid) {
ans = Math.max(ans, query(u << 1 | 1, l, r));
}
return ans;
}
private void pushup(int u) {
Node root = tr[u];
Node left = tr[u << 1], right = tr[u << 1 | 1];
root.mx = Math.max(left.mx, right.mx);
root.lmx = left.lmx;
root.rmx = right.rmx;
int a = left.r - left.l + 1;
int b = right.r - right.l + 1;
if (s[left.r - 1] == s[right.l - 1]) {
if (left.lmx == a) {
root.lmx += right.lmx;
}
if (right.rmx == b) {
root.rmx += left.rmx;
}
root.mx = Math.max(root.mx, left.rmx + right.lmx);
}
}
}
class Solution {
public int[] longestRepeating(String s, String queryCharacters, int[] queryIndices) {
SegmentTree tree = new SegmentTree(s.toCharArray());
int k = queryIndices.length;
int[] ans = new int[k];
int n = s.length();
for (int i = 0; i < k; ++i) {
int x = queryIndices[i] + 1;
char v = queryCharacters.charAt(i);
tree.modify(1, x, v);
ans[i] = tree.query(1, 1, n);
}
return ans;
}
}class Node {
public:
int l, r;
int lmx, rmx, mx;
Node(int l, int r)
: l(l)
, r(r)
, lmx(1)
, rmx(1)
, mx(1) {}
};
class SegmentTree {
private:
string s;
vector<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);
pushup(u);
}
void pushup(int u) {
Node* root = tr[u];
Node* left = tr[u << 1];
Node* right = tr[u << 1 | 1];
root->mx = max(left->mx, right->mx);
root->lmx = left->lmx;
root->rmx = right->rmx;
int a = left->r - left->l + 1;
int b = right->r - right->l + 1;
if (s[left->r - 1] == 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);
}
}
public:
SegmentTree(const string& s)
: s(s) {
int n = s.size();
tr.resize(n * 4);
build(1, 1, n);
}
void modify(int u, int x, char v) {
if (tr[u]->l == x && tr[u]->r == x) {
s[x - 1] = v;
return;
}
int mid = (tr[u]->l + tr[u]->r) >> 1;
if (x <= mid) {
modify(u << 1, x, v);
} else {
modify(u << 1 | 1, x, v);
}
pushup(u);
}
int query(int u, int l, int r) {
if (tr[u]->l >= l && tr[u]->r <= r) {
return tr[u]->mx;
}
int mid = (tr[u]->l + tr[u]->r) >> 1;
int ans = 0;
if (r <= mid) {
ans = query(u << 1, l, r);
} else if (l > mid) {
ans = max(ans, query(u << 1 | 1, l, r));
}
return ans;
}
};
class Solution {
public:
vector<int> longestRepeating(string s, string queryCharacters, vector<int>& queryIndices) {
SegmentTree tree(s);
int k = queryIndices.size();
vector<int> ans(k);
int n = s.size();
for (int i = 0; i < k; ++i) {
int x = queryIndices[i] + 1;
char v = queryCharacters[i];
tree.modify(1, x, v);
ans[i] = tree.query(1, 1, n);
}
return ans;
}
};type Node struct {
l, r int
lmx, rmx, mx int
}
type SegmentTree struct {
s []byte
tr []*Node
}
func NewNode(l, r int) *Node {
return &Node{l: l, r: r, lmx: 1, rmx: 1, mx: 1}
}
func NewSegmentTree(s string) *SegmentTree {
n := len(s)
tree := &SegmentTree{s: []byte(s), tr: make([]*Node, n<<2)}
tree.build(1, 1, n)
return tree
}
func (tree *SegmentTree) build(u, l, r int) {
tree.tr[u] = NewNode(l, r)
if l == r {
return
}
mid := (l + r) >> 1
tree.build(u<<1, l, mid)
tree.build(u<<1|1, mid+1, r)
tree.pushup(u)
}
func (tree *SegmentTree) modify(u, x int, v byte) {
if tree.tr[u].l == x && tree.tr[u].r == x {
tree.s[x-1] = v
return
}
mid := (tree.tr[u].l + tree.tr[u].r) >> 1
if x <= mid {
tree.modify(u<<1, x, v)
} else {
tree.modify(u<<1|1, x, v)
}
tree.pushup(u)
}
func (tree *SegmentTree) query(u, l, r int) int {
if tree.tr[u].l >= l && tree.tr[u].r <= r {
return tree.tr[u].mx
}
mid := (tree.tr[u].l + tree.tr[u].r) >> 1
ans := 0
if r <= mid {
ans = tree.query(u<<1, l, r)
} else if l > mid {
ans = max(ans, tree.query(u<<1|1, l, r))
} else {
ans = max(tree.query(u<<1, l, r), tree.query(u<<1|1, l, r))
}
return ans
}
func (tree *SegmentTree) pushup(u int) {
root := tree.tr[u]
left := tree.tr[u<<1]
right := tree.tr[u<<1|1]
root.mx = max(left.mx, right.mx)
root.lmx = left.lmx
root.rmx = right.rmx
a := left.r - left.l + 1
b := right.r - right.l + 1
if tree.s[left.r-1] == tree.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)
}
}
func longestRepeating(s string, queryCharacters string, queryIndices []int) (ans []int) {
tree := NewSegmentTree(s)
n := len(s)
for i, v := range queryCharacters {
x := queryIndices[i] + 1
tree.modify(1, x, byte(v))
ans = append(ans, tree.query(1, 1, n))
}
return
}class Node {
l: number;
r: number;
lmx: number;
rmx: number;
mx: number;
constructor(l: number, r: number) {
this.l = l;
this.r = r;
this.lmx = 1;
this.rmx = 1;
this.mx = 1;
}
}
class SegmentTree {
private s: string[];
private tr: Node[];
constructor(s: string) {
this.s = s.split('');
this.tr = Array(s.length * 4)
.fill(null)
.map(() => new Node(0, 0));
this.build(1, 1, s.length);
}
private build(u: number, l: number, r: number): void {
this.tr[u] = new Node(l, r);
if (l === r) {
return;
}
const mid = (l + r) >> 1;
this.build(u << 1, l, mid);
this.build((u << 1) | 1, mid + 1, r);
this.pushup(u);
}
public modify(u: number, x: number, v: string): void {
if (this.tr[u].l === x && this.tr[u].r === x) {
this.s[x - 1] = v;
return;
}
const mid = (this.tr[u].l + this.tr[u].r) >> 1;
if (x <= mid) {
this.modify(u << 1, x, v);
} else {
this.modify((u << 1) | 1, x, v);
}
this.pushup(u);
}
public query(u: number, l: number, r: number): number {
if (this.tr[u].l >= l && this.tr[u].r <= r) {
return this.tr[u].mx;
}
const mid = (this.tr[u].l + this.tr[u].r) >> 1;
let ans = 0;
if (r <= mid) {
ans = this.query(u << 1, l, r);
} else if (l > mid) {
ans = Math.max(ans, this.query((u << 1) | 1, l, r));
} else {
ans = Math.max(this.query(u << 1, l, r), this.query((u << 1) | 1, l, r));
}
return ans;
}
private pushup(u: number): void {
const root = this.tr[u];
const left = this.tr[u << 1];
const right = this.tr[(u << 1) | 1];
root.mx = Math.max(left.mx, right.mx);
root.lmx = left.lmx;
root.rmx = right.rmx;
const a = left.r - left.l + 1;
const b = right.r - right.l + 1;
if (this.s[left.r - 1] === this.s[right.l - 1]) {
if (left.lmx === a) {
root.lmx += right.lmx;
}
if (right.rmx === b) {
root.rmx += left.rmx;
}
root.mx = Math.max(root.mx, left.rmx + right.lmx);
}
}
}
function longestRepeating(s: string, queryCharacters: string, queryIndices: number[]): number[] {
const tree = new SegmentTree(s);
const k = queryIndices.length;
const ans: number[] = new Array(k);
const n = s.length;
for (let i = 0; i < k; ++i) {
const x = queryIndices[i] + 1;
const v = queryCharacters[i];
tree.modify(1, x, v);
ans[i] = tree.query(1, 1, n);
}
return ans;
}