# Longest Substring of One Repeating Character
**Difficulty:** HARD
[External](https://leetcode.com/problems/longest-substring-of-one-repeating-character)
Canonical: https://scaleengineer.com/dsa/problems/longest-substring-of-one-repeating-character
**Data structures:** Array, String, Segment Tree, Ordered Set
---
## 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 = "b**b**bacc". The longest substring consisting of one repeating character is "bbb" with length 3.
- 2nd query updates s = "bbb**c**cc". 
  The longest substring consisting of one repeating character can be "bbb" or "ccc" with length 3.
- 3rd query updates s = "bbb**b**cc". 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 = "ab**a**zz". The longest substring consisting of one repeating character is "zz" with length 2.
- 2nd query updates s = "a**a**azz". The longest substring consisting of one repeating character is "aaa" with length 3.
Thus, we return [2,3].

**Constraints:**

* `1 <= s.length <= 105`
* `s` consists of lowercase English letters.
* `k == queryCharacters.length == queryIndices.length`
* `1 <= k <= 105`
* `queryCharacters` consists of lowercase English letters.
* `0 <= queryIndices[i] < s.length`

# Approaches
## Brute Force Re-computation
This approach directly simulates the process described in the problem. For each query, it first updates the character in the string. Then, it performs a full linear scan of the entire modified string to find the length of the longest substring composed of a single repeating character.
**Time:** O(k * n), where `n` is the length of `s` and `k` is the number of queries. For each of the `k` queries, we scan the entire string of length `n`. This is too slow for the given constraints. · **Space:** O(n + k), where `n` is the length of the string and `k` is the number of queries. We need O(n) space for the character array and O(k) space for the result array.
**Pros:** Simple to understand and implement.; Requires minimal auxiliary data structures, making it memory-efficient in terms of extra space.
**Cons:** Extremely inefficient for the given constraints, leading to a 'Time Limit Exceeded' verdict on most platforms.; It re-computes the result from scratch for every query, failing to leverage the fact that each update only affects the string locally.
### Explanation
The brute-force method is the most straightforward way to solve the problem. We begin by converting the string `s` into a more flexible data structure like a character array, which allows for O(1) time complexity for character updates.

For each of the `k` queries, we perform two main steps:
1.  **Update**: We change the character at the specified `queryIndices[i]` to the new `queryCharacters[i]`.
2.  **Recalculate**: We iterate through the entire character array from beginning to end. We use a variable, say `currentLength`, to keep track of the length of the current substring of repeating characters. Another variable, `maxLength`, stores the maximum length found so far. As we iterate, if we encounter a character that is the same as the previous one, we increment `currentLength`. If the character changes, we reset `currentLength` to 1. At each step, we update `maxLength` to be the maximum of its current value and `currentLength`. 

After scanning the whole array, `maxLength` will hold the answer for the current query. We store this value and proceed to the next query. This entire process is repeated for all `k` queries.

```java
class Solution {
    public int[] longestRepeating(String s, String queryCharacters, int[] queryIndices) {
        int k = queryIndices.length;
        int[] ans = new int[k];
        char[] sChars = s.toCharArray();

        for (int i = 0; i < k; i++) {
            sChars[queryIndices[i]] = queryCharacters.charAt(i);
            
            int maxLength = 0;
            if (sChars.length > 0) {
                maxLength = 1;
                int currentLength = 1;
                for (int j = 1; j < sChars.length; j++) {
                    if (sChars[j] == sChars[j - 1]) {
                        currentLength++;
                    } else {
                        currentLength = 1;
                    }
                    maxLength = Math.max(maxLength, currentLength);
                }
            }
            ans[i] = maxLength;
        }
        return ans;
    }
}
```
### Algorithm
- Convert the input string `s` to a mutable `char` array, `sChars`.
- Initialize an integer array `result` of size `k` to store the answers.
- Loop through each query from `i = 0` to `k-1`:
  - Update the character in `sChars` at the given index: `sChars[queryIndices[i]] = queryCharacters.charAt(i)`.
  - Initialize `maxLength = 0`, `currentLength = 0`.
  - Perform a linear scan through the `sChars` array.
  - During the scan, track the length of the current contiguous block of identical characters.
  - If `sChars[j]` is the same as `sChars[j-1]`, increment `currentLength`. Otherwise, reset `currentLength` to 1.
  - Continuously update `maxLength` with the maximum `currentLength` seen so far.
  - After the scan, store the final `maxLength` in `result[i]`.
- Return the `result` array.

## Interval Management with Balanced Binary Search Trees
This optimized approach avoids re-scanning the entire string. It intelligently maintains the contiguous blocks (intervals) of same characters and their lengths using balanced binary search trees (`TreeMap` in Java). When a character is updated, it only adjusts the specific intervals affected by the change, which is significantly faster.
**Time:** O(n + k * log n). The initial processing of the string takes O(n). Each query involves a constant number of `TreeMap` operations (lookups, insertions, deletions), each taking O(log N_blocks) time. Since the number of blocks `N_blocks` is at most `n`, each query is O(log n). · **Space:** O(n + k). In the worst case (e.g., a string like "ababab..."), we might have `n` distinct blocks, so the `intervals` and `lengths` maps can take up to O(n) space. O(k) is for the result array.
**Pros:** Highly efficient, with logarithmic time complexity per query.; Correctly models the problem by only updating locally affected data.; Scales well for large inputs, easily passing the given constraints.
**Cons:** The logic for splitting and merging intervals can be complex and tricky to implement correctly without bugs.; Java's `TreeMap` has higher constant factors and memory overhead compared to array-based structures like a segment tree, which might result in slightly slower practical performance.
### Explanation
Instead of re-evaluating the entire string, we can focus only on the changes. An update at index `idx` can only affect the block of repeating characters that contains `idx` and potentially its immediate neighbors.

We use two `TreeMap` data structures to efficiently manage this:
1.  `intervals`: A `TreeMap<Integer, Integer>` that maps the starting index of a block to its ending index. The sorted nature of `TreeMap` allows us to find which block an index `idx` belongs to in `O(log N_blocks)` time using `floorEntry(idx)`.
2.  `lengths`: A `TreeMap<Integer, Integer>` that serves as a multiset, mapping each block length to the count of blocks having that length. This lets us find the maximum length in `O(log L_distinct)` time by getting the last key (`lastKey()`).

**Initialization**: We first scan the string `s` once to identify all initial blocks and populate `intervals` and `lengths`.

**Query Processing**: For each query, we perform a two-phase update:
1.  **Decomposition**: The character update at `idx` will break the block it currently belongs to. We find this block, remove it from our data structures, and add back the two smaller pieces it splits into (e.g., `[start, idx-1]` and `[idx+1, end]`).
2.  **Composition**: After updating the character array, the new character at `idx` forms a new block of length 1. This block might be able to merge with its left and/or right neighbors if they now share the same character. We check for this, and if merges are possible, we remove the old, smaller blocks and add the new, larger merged block.

After these adjustments, the maximum length is simply the largest key present in our `lengths` map.

```java
import java.util.TreeMap;
import java.util.Map;

class Solution {
    char[] sArr;
    TreeMap<Integer, Integer> intervals; // {start -> end}
    TreeMap<Integer, Integer> lengths;   // {length -> count}

    public int[] longestRepeating(String s, String queryCharacters, int[] queryIndices) {
        sArr = s.toCharArray();
        int n = s.length();
        intervals = new TreeMap<>();
        lengths = new TreeMap<>();

        // Initial build
        int start = 0;
        for (int i = 1; i <= n; i++) {
            if (i == n || sArr[i] != sArr[start]) {
                addInterval(start, i - 1);
                start = i;
            }
        }

        int k = queryIndices.length;
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            int idx = queryIndices[i];
            char newChar = queryCharacters.charAt(i);

            if (sArr[idx] != newChar) {
                // --- Decomposition ---
                Map.Entry<Integer, Integer> entry = intervals.floorEntry(idx);
                int oldStart = entry.getKey();
                int oldEnd = entry.getValue();
                
                removeInterval(oldStart, oldEnd);

                if (idx > oldStart) {
                    addInterval(oldStart, idx - 1);
                }
                if (idx < oldEnd) {
                    addInterval(idx + 1, oldEnd);
                }

                // --- Composition ---
                sArr[idx] = newChar;
                int newStart = idx;
                int newEnd = idx;

                // Merge with left
                Map.Entry<Integer, Integer> leftEntry = intervals.floorEntry(idx - 1);
                if (leftEntry != null && leftEntry.getValue() == idx - 1 && sArr[idx - 1] == newChar) {
                    newStart = leftEntry.getKey();
                    removeInterval(newStart, idx - 1);
                }

                // Merge with right
                Integer rightEnd = intervals.get(idx + 1);
                if (rightEnd != null && sArr[idx + 1] == newChar) {
                    newEnd = rightEnd;
                    removeInterval(idx + 1, newEnd);
                }
                
                addInterval(newStart, newEnd);
            }
            
            result[i] = lengths.isEmpty() ? 0 : lengths.lastKey();
        }
        return result;
    }

    private void addInterval(int start, int end) {
        intervals.put(start, end);
        int len = end - start + 1;
        lengths.put(len, lengths.getOrDefault(len, 0) + 1);
    }

    private void removeInterval(int start, int end) {
        intervals.remove(start);
        int len = end - start + 1;
        lengths.put(len, lengths.get(len) - 1);
        if (lengths.get(len) == 0) {
            lengths.remove(len);
        }
    }
}
```
### Algorithm
- Initialize two `TreeMap`s: `intervals` to map a block's start index to its end index, and `lengths` to map a block's length to its frequency.
- Pre-process the initial string `s` in O(n) time to populate both `TreeMap`s with the initial blocks.
- For each query `(idx, newChar)`:
  - If the character at `idx` is not changing, the answer remains the same.
  - **Decomposition**: Find the block `[start, end]` containing `idx` using `intervals.floorEntry(idx)`. Remove this block from `intervals` and its length from `lengths`. Add back the two potential sub-blocks `[start, idx-1]` and `[idx+1, end]` if they are non-empty.
  - Update the character in the underlying character array: `sArr[idx] = newChar`.
  - **Composition**: A new block of length 1 is formed at `idx`. Check if this block can be merged with an adjacent block to the left (ending at `idx-1`) or to the right (starting at `idx+1`) if they consist of `newChar`. If a merge is possible, remove the old smaller blocks and add the new, larger merged block to the `TreeMap`s.
  - The answer for the query is the largest key in the `lengths` map, which can be retrieved with `lengths.lastKey()`.
- Store the answer and repeat for all queries.

## Segment Tree
A segment tree is a powerful data structure well-suited for problems involving point updates and range queries. We build a segment tree over the string, where each node stores aggregated information about the longest repeating character substring within its corresponding range. An update to the string translates to an update on a single leaf of the tree, with changes efficiently propagated up to the root.
**Time:** O(n + k * log n). Building the tree takes O(n) time. Each update requires traversing the height of the tree, which is O(log n). With `k` updates, the total time is dominated by the queries. · **Space:** O(n + k). The segment tree itself requires O(n) space (typically an array of size `4n` is allocated for simplicity). O(k) is for the result array.
**Pros:** Highly efficient, with O(log n) time complexity per update.; A standard and very powerful technique for problems involving point updates and range queries.; Often has better practical performance than `TreeMap`-based solutions due to its array-based implementation, which leads to better cache locality.
**Cons:** The implementation is more complex than the brute-force approach, particularly the `merge` logic, which requires careful handling of all cases.; It requires more memory than the brute-force approach, typically an array of size `4n` to store the tree nodes.
### Explanation
This approach uses a segment tree, a classic data structure for this type of problem. Each node in the tree represents a range `[L, R]` of the string and stores crucial information about it.

For each node, we store:
- `maxLen`: The length of the longest repeating character substring fully contained within `s[L...R]`.
- `prefixLen`, `prefixChar`: The length and character of the uniform prefix of `s[L...R]`.
- `suffixLen`, `suffixChar`: The length and character of the uniform suffix of `s[L...R]`.
- `len`: The total length of the range, `R - L + 1`.

**Build**: The tree is built recursively. A leaf node for index `i` will have `maxLen=1`, `prefixLen=1`, `suffixLen=1`, etc. Parent nodes are formed by a `merge` function that combines information from its left and right children.

**Merge Logic**: The key is the `merge` function. The `maxLen` of a parent is the maximum of `left.maxLen`, `right.maxLen`, and a potential new maximum formed by joining the suffix of the left child with the prefix of the right child, which is possible only if `left.suffixChar == right.prefixChar`. The prefix and suffix of the parent are also computed based on whether they can extend across the child boundary.

**Update**: An update to `s[idx]` corresponds to updating a single leaf in the segment tree. We traverse down to the leaf, change its value, and then traverse back up to the root, applying the `merge` logic at each level to update the ancestor nodes.

**Query**: After each update, the answer for the entire string is readily available as the `maxLen` value stored in the root node of the segment tree.

```java
class Solution {
    class Node {
        int maxLen;
        int prefixLen, suffixLen;
        char prefixChar, suffixChar;
        int len;

        Node(int maxLen, int prefixLen, char prefixChar, int suffixLen, char suffixChar, int len) {
            this.maxLen = maxLen;
            this.prefixLen = prefixLen;
            this.prefixChar = prefixChar;
            this.suffixLen = suffixLen;
            this.suffixChar = suffixChar;
            this.len = len;
        }
    }

    Node[] tree;
    char[] sArr;

    public int[] longestRepeating(String s, String queryCharacters, int[] queryIndices) {
        int n = s.length();
        sArr = s.toCharArray();
        tree = new Node[4 * n];
        build(0, 0, n - 1);

        int k = queryIndices.length;
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            int idx = queryIndices[i];
            char ch = queryCharacters.charAt(i);
            update(0, 0, n - 1, idx, ch);
            result[i] = tree[0].maxLen;
        }
        return result;
    }

    private Node merge(Node left, Node right) {
        if (left == null) return right;
        if (right == null) return left;

        int maxLen = Math.max(left.maxLen, right.maxLen);
        if (left.suffixChar == right.prefixChar) {
            maxLen = Math.max(maxLen, left.suffixLen + right.prefixLen);
        }

        int prefixLen = left.prefixLen;
        char prefixChar = left.prefixChar;
        if (left.prefixLen == left.len && left.prefixChar == right.prefixChar) {
            prefixLen += right.prefixLen;
        }

        int suffixLen = right.suffixLen;
        char suffixChar = right.suffixChar;
        if (right.suffixLen == right.len && right.suffixChar == left.suffixChar) {
            suffixLen += left.suffixLen;
        }
        
        return new Node(maxLen, prefixLen, prefixChar, suffixLen, suffixChar, left.len + right.len);
    }

    private void build(int node, int start, int end) {
        if (start == end) {
            tree[node] = new Node(1, 1, sArr[start], 1, sArr[start], 1);
            return;
        }
        int mid = start + (end - start) / 2;
        build(2 * node + 1, start, mid);
        build(2 * node + 2, mid + 1, end);
        tree[node] = merge(tree[2 * node + 1], tree[2 * node + 2]);
    }

    private void update(int node, int start, int end, int idx, char val) {
        if (start == end) {
            sArr[idx] = val;
            tree[node] = new Node(1, 1, val, 1, val, 1);
            return;
        }
        int mid = start + (end - start) / 2;
        if (start <= idx && idx <= mid) {
            update(2 * node + 1, start, mid, idx, val);
        } else {
            update(2 * node + 2, mid + 1, end, idx, val);
        }
        tree[node] = merge(tree[2 * node + 1], tree[2 * node + 2]);
    }
}
```
### Algorithm
- Define a `Node` class to store segment information: `maxLen`, `prefixLen`, `prefixChar`, `suffixLen`, `suffixChar`, and total `len`.
- Implement a `merge(leftNode, rightNode)` function that combines two child nodes into a parent node, calculating the parent's attributes based on the children's.
- Implement a `build(s, ...)` function to recursively construct the segment tree from the bottom up. Leaf nodes correspond to single characters of `s`.
- Implement an `update(idx, char, ...)` function. When a query arrives, this function finds the corresponding leaf in the tree, updates its value, and then propagates the changes up to the root by calling the `merge` function on each parent along the path.
- For each query, call `update()` and then the answer is simply the `maxLen` value stored in the root of the tree (`tree[0]`).

# Solutions
### Java

```java
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 ; } }
```

### CPP

```cpp
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 ; } };
```

### Python

```python
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
```