Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2213.html
2213. Longest Substring of One Repeating Character
- Difficulty: Hard.
- Related Topics: Array, String, Segment Tree, Ordered Set.
- Similar Questions: Merge Intervals, Longest Repeating Character Replacement, Consecutive Characters, Create Sorted Array through Instructions.
Problem
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 <= 105 -
sconsists of lowercase English letters. -
k == queryCharacters.length == queryIndices.length -
1 <= k <= 105 -
queryCharactersconsists of lowercase English letters. -
0 <= queryIndices[i] < s.length
Solution
-
class Solution { static class TreeNode { int start; int end; char leftChar; int leftCharLen; char rightChar; int rightCharLen; int max; TreeNode left; TreeNode right; TreeNode(int start, int end) { this.start = start; this.end = end; left = null; right = null; } } public int[] longestRepeating(String s, String queryCharacters, int[] queryIndices) { char[] sChar = s.toCharArray(); char[] qChar = queryCharacters.toCharArray(); TreeNode root = buildTree(sChar, 0, sChar.length - 1); int[] result = new int[qChar.length]; for (int i = 0; i < qChar.length; i++) { updateTree(root, queryIndices[i], qChar[i]); if (root != null) { result[i] = root.max; } } return result; } private TreeNode buildTree(char[] s, int from, int to) { if (from > to) { return null; } TreeNode root = new TreeNode(from, to); if (from == to) { root.max = 1; root.rightChar = root.leftChar = s[from]; root.leftCharLen = root.rightCharLen = 1; return root; } int middle = from + (to - from) / 2; root.left = buildTree(s, from, middle); root.right = buildTree(s, middle + 1, to); updateNode(root); return root; } private void updateTree(TreeNode root, int index, char c) { if (root == null || root.start > index || root.end < index) { return; } if (root.start == index && root.end == index) { root.leftChar = root.rightChar = c; return; } updateTree(root.left, index, c); updateTree(root.right, index, c); updateNode(root); } private void updateNode(TreeNode root) { if (root == null) { return; } root.leftChar = root.left.leftChar; root.leftCharLen = root.left.leftCharLen; root.rightChar = root.right.rightChar; root.rightCharLen = root.right.rightCharLen; root.max = Math.max(root.left.max, root.right.max); if (root.left.rightChar == root.right.leftChar) { int len = root.left.rightCharLen + root.right.leftCharLen; if (root.left.leftChar == root.left.rightChar && root.left.leftCharLen == root.left.end - root.left.start + 1) { root.leftCharLen = len; } if (root.right.leftChar == root.right.rightChar && root.right.leftCharLen == root.right.end - root.right.start + 1) { root.rightCharLen = len; } root.max = Math.max(root.max, len); } } } -
Todo -
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 ############ # 2213. Longest Substring of One Repeating Character # https://leetcode.com/problems/longest-substring-of-one-repeating-character/ from sortedcontainers import SortedList class Solution: def longestRepeating(self, s: str, qc: str, qi: List[int]) -> List[int]: M = 10 ** 6 n = len(s) k = len(qc) s = list(s) sl = SortedList() h = SortedList() curr = 0 for x, group in groupby(s): length = sum(1 for c in group) sl.add((curr, curr + length - 1)) h.add(length) curr += length def add(x, y): sl.add((x, y)) h.add(y - x + 1) def remove(x, y): sl.remove((x, y)) h.remove(y - x + 1) def split(i): index = sl.bisect_right((i, M)) - 1 left, right = sl[index] remove(left, right) if left != i: add(left, i - 1) add(i, i) if right != i: add(i + 1, right) def merge(index): if index + 1 >= len(sl): return left1, right1 = sl[index] left2, right2 = sl[index + 1] if s[right1] != s[left2]: return remove(left1, right1) remove(left2, right2) add(left1, right2) res = [] for i, c in zip(qi, qc): if s[i] == c: res.append(h[-1]) continue split(i) index = sl.bisect_right((i, M)) - 1 s[i] = c merge(index) if index - 1 >= 0: merge(index - 1) res.append(h[-1]) return res
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).