Welcome to Subscribe On Youtube
2213. Longest Substring of One Repeating Character
Description
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
Solutions
Segment Tree.
-
class Node { int l; int r; int size; int lmx; int rmx; int mx; char lc; char rc; } class SegmentTree { private String s; private Node[] tr; public SegmentTree(String s) { int n = s.length(); this.s = s; tr = new Node[n << 2]; for (int i = 0; i < tr.length; ++i) { tr[i] = new Node(); } build(1, 1, n); } public void build(int u, int l, int r) { tr[u].l = l; tr[u].r = r; if (l == r) { tr[u].lmx = 1; tr[u].rmx = 1; tr[u].mx = 1; tr[u].size = 1; tr[u].lc = s.charAt(l - 1); tr[u].rc = s.charAt(l - 1); return; } int mid = (l + r) >> 1; build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r); pushup(u); } void modify(int u, int x, char v) { if (tr[u].l == x && tr[u].r == x) { tr[u].lc = v; tr[u].rc = 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); } Node query(int u, int l, int r) { if (tr[u].l >= l && tr[u].r <= r) { return tr[u]; } int mid = (tr[u].l + tr[u].r) >> 1; if (r <= mid) { return query(u << 1, l, r); } if (l > mid) { return query(u << 1 | 1, l, r); } Node ans = new Node(); Node left = query(u << 1, l, r); Node right = query(u << 1 | 1, l, r); pushup(ans, left, right); return ans; } void pushup(Node root, Node left, Node right) { root.lc = left.lc; root.rc = right.rc; root.size = left.size + right.size; root.mx = Math.max(left.mx, right.mx); root.lmx = left.lmx; root.rmx = right.rmx; if (left.rc == right.lc) { if (left.lmx == left.size) { root.lmx += right.lmx; } if (right.rmx == right.size) { root.rmx += left.rmx; } root.mx = Math.max(root.mx, left.rmx + right.lmx); } } void pushup(int u) { pushup(tr[u], tr[u << 1], tr[u << 1 | 1]); } } class Solution { public int[] longestRepeating(String s, String queryCharacters, int[] queryIndices) { SegmentTree tree = new SegmentTree(s); int k = queryCharacters.length(); int[] ans = new int[k]; for (int i = 0; i < k; ++i) { int x = queryIndices[i] + 1; char c = queryCharacters.charAt(i); tree.modify(1, x, c); ans[i] = tree.query(1, 1, s.length()).mx; } return ans; } } -
class Node { public: int l, r, size, lmx, rmx, mx; char lc, rc; }; class SegmentTree { private: string s; vector<Node*> tr; public: SegmentTree(string& s) { this->s = s; int n = s.size(); tr.resize(n << 2); for (int i = 0; i < tr.size(); ++i) tr[i] = new Node(); build(1, 1, n); } void build(int u, int l, int r) { tr[u]->l = l; tr[u]->r = r; if (l == r) { tr[u]->lmx = tr[u]->rmx = tr[u]->mx = tr[u]->size = 1; tr[u]->lc = tr[u]->rc = s[l - 1]; return; } int mid = (l + r) >> 1; build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r); pushup(u); } void modify(int u, int x, char v) { if (tr[u]->l == x && tr[u]->r == x) { tr[u]->lc = tr[u]->rc = 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); } Node* query(int u, int l, int r) { if (tr[u]->l >= l && tr[u]->r <= r) return tr[u]; int mid = (tr[u]->l + tr[u]->r) >> 1; if (r <= mid) return query(u << 1, l, r); if (l > mid) query(u << 1 | 1, l, r); Node* ans = new Node(); Node* left = query(u << 1, l, r); Node* right = query(u << 1 | 1, l, r); pushup(ans, left, right); return ans; } void pushup(Node* root, Node* left, Node* right) { root->lc = left->lc; root->rc = right->rc; root->size = left->size + right->size; root->mx = max(left->mx, right->mx); root->lmx = left->lmx; root->rmx = right->rmx; if (left->rc == right->lc) { if (left->lmx == left->size) root->lmx += right->lmx; if (right->rmx == right->size) root->rmx += left->rmx; root->mx = max(root->mx, left->rmx + right->lmx); } } void pushup(int u) { pushup(tr[u], tr[u << 1], tr[u << 1 | 1]); } }; class Solution { public: vector<int> longestRepeating(string s, string queryCharacters, vector<int>& queryIndices) { SegmentTree* tree = new SegmentTree(s); int k = queryCharacters.size(); vector<int> ans(k); for (int i = 0; i < k; ++i) { int x = queryIndices[i] + 1; tree->modify(1, x, queryCharacters[i]); ans[i] = tree->query(1, 1, s.size())->mx; } return ans; } }; -
class Node: def __init__(self): self.l = 0 self.r = 0 self.lmx = 0 self.rmx = 0 self.mx = 0 self.size = 0 self.lc = None self.rc = None N = 100010 tr = [Node() for _ in range(N << 2)] class SegmentTree: def __init__(self, s): n = len(s) self.s = s self.build(1, 1, n) def build(self, u, l, r): tr[u].l = l tr[u].r = r if l == r: tr[u].lmx = tr[u].rmx = tr[u].mx = tr[u].size = 1 tr[u].lc = tr[u].rc = self.s[l - 1] return mid = (l + r) >> 1 self.build(u << 1, l, mid) self.build(u << 1 | 1, mid + 1, r) self.pushup(u) def modify(self, u, x, v): if tr[u].l == x and tr[u].r == x: tr[u].lc = tr[u].rc = v return mid = (tr[u].l + tr[u].r) >> 1 if x <= mid: self.modify(u << 1, x, v) else: self.modify(u << 1 | 1, x, v) self.pushup(u) def query(self, u, l, r): if tr[u].l >= l and tr[u].r <= r: return tr[u] mid = (tr[u].l + tr[u].r) >> 1 if r <= mid: return self.query(u << 1, l, r) if l > mid: return self.query(u << 1 | 1, l, r) left, right = self.query(u << 1, l, r), self.query(u << 1 | 1, l, r) ans = Node() self._pushup(ans, left, right) return ans def _pushup(self, root, left, right): root.lc, root.rc = left.lc, right.rc root.size = left.size + right.size root.mx = max(left.mx, right.mx) root.lmx, root.rmx = left.lmx, right.rmx if left.rc == right.lc: if left.lmx == left.size: root.lmx += right.lmx if right.rmx == right.size: root.rmx += left.rmx root.mx = max(root.mx, left.rmx + right.lmx) def pushup(self, u): self._pushup(tr[u], tr[u << 1], tr[u << 1 | 1]) class Solution: def longestRepeating( self, s: str, queryCharacters: str, queryIndices: List[int] ) -> List[int]: tree = SegmentTree(s) k = len(queryIndices) ans = [] for i, c in enumerate(queryCharacters): x = queryIndices[i] + 1 tree.modify(1, x, c) ans.append(tree.query(1, 1, len(s)).mx) return ans -
type segmentTree struct { str []byte mx []int lmx []int rmx []int } func newSegmentTree(s string) *segmentTree { n := len(s) t := &segmentTree{ str: []byte(s), mx: make([]int, n<<2), lmx: make([]int, n<<2), rmx: make([]int, n<<2), } t.build(0, 0, n-1) return t } func (t *segmentTree) build(x, l, r int) { if l == r { t.lmx[x] = 1 t.rmx[x] = 1 t.mx[x] = 1 return } m := int(uint(l+r) >> 1) t.build(x*2+1, l, m) t.build(x*2+2, m+1, r) t.pushup(x, l, m, r) } func (t *segmentTree) pushup(x, l, m, r int) { lch, rch := x*2+1, x*2+2 t.lmx[x] = t.lmx[lch] t.rmx[x] = t.rmx[rch] t.mx[x] = max(t.mx[lch], t.mx[rch]) // can be merged if t.str[m] == t.str[m+1] { if t.lmx[lch] == m-l+1 { t.lmx[x] += t.lmx[rch] } if t.rmx[rch] == r-m { t.rmx[x] += t.rmx[lch] } t.mx[x] = max(t.mx[x], t.rmx[lch]+t.lmx[rch]) } } func (t *segmentTree) update(x, l, r, pos int, val byte) { if l == r { t.str[pos] = val return } m := int(uint(l+r) >> 1) if pos <= m { t.update(x*2+1, l, m, pos, val) } else { t.update(x*2+2, m+1, r, pos, val) } t.pushup(x, l, m, r) } func longestRepeating(s string, queryCharacters string, queryIndices []int) []int { ans := make([]int, len(queryCharacters)) t := newSegmentTree(s) n := len(s) for i, c := range queryCharacters { t.update(0, 0, n-1, queryIndices[i], byte(c)) ans[i] = t.mx[0] } return ans } -
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; } -
impl Solution { pub fn longest_repeating( s: String, query_characters: String, query_indices: Vec<i32>, ) -> Vec<i32> { struct Node { l: usize, r: usize, lmx: i32, rmx: i32, mx: i32, } struct SegmentTree { s: Vec<u8>, tr: Vec<Node>, } impl SegmentTree { fn new(s: String) -> Self { let n = s.len(); let mut tree = Self { s: s.into_bytes(), tr: (0..n * 4 + 5) .map(|_| Node { l: 0, r: 0, lmx: 0, rmx: 0, mx: 0, }) .collect(), }; tree.build(1, 1, n); tree } fn build(&mut self, u: usize, l: usize, r: usize) { self.tr[u] = Node { l, r, lmx: 1, rmx: 1, mx: 1, }; if l == r { return; } let mid = (l + r) >> 1; self.build(u << 1, l, mid); self.build(u << 1 | 1, mid + 1, r); self.pushup(u); } fn modify(&mut self, u: usize, x: usize, v: u8) { if self.tr[u].l == self.tr[u].r { self.s[x - 1] = v; return; } let mid = (self.tr[u].l + self.tr[u].r) >> 1; if x <= mid { self.modify(u << 1, x, v); } else { self.modify(u << 1 | 1, x, v); } self.pushup(u); } fn pushup(&mut self, u: usize) { let left = u << 1; let right = u << 1 | 1; let left_lmx = self.tr[left].lmx; let left_rmx = self.tr[left].rmx; let left_mx = self.tr[left].mx; let right_lmx = self.tr[right].lmx; let right_rmx = self.tr[right].rmx; let right_mx = self.tr[right].mx; self.tr[u].lmx = left_lmx; self.tr[u].rmx = right_rmx; self.tr[u].mx = left_mx.max(right_mx); let left_len = self.tr[left].r - self.tr[left].l + 1; let right_len = self.tr[right].r - self.tr[right].l + 1; if self.s[self.tr[left].r - 1] == self.s[self.tr[right].l - 1] { if left_lmx as usize == left_len { self.tr[u].lmx += right_lmx; } if right_rmx as usize == right_len { self.tr[u].rmx += left_rmx; } self.tr[u].mx = self.tr[u].mx.max(left_rmx + right_lmx); } } fn query(&self) -> i32 { self.tr[1].mx } } let mut tree = SegmentTree::new(s); let mut ans = Vec::with_capacity(query_indices.len()); for (x, v) in query_indices.iter().zip(query_characters.bytes()) { tree.modify(1, *x as usize + 1, v); ans.push(tree.query()); } ans } }