2213. Longest Substring of One Repeating Character

Problem Description

You are given a string s (0-indexed) and need to process k queries on it. Each query updates a single character in the string.

For each query i, you:

Replace the character at position queryIndices[i] with the character queryCharacters[i]

After each query, you need to find the length of the longest substring that consists of only one repeating character in the entire modified string.

Input:

A string s
A string queryCharacters of length k containing the new characters for each query
An array queryIndices of length k containing the positions to update for each query

Output:

An array lengths of length k where lengths[i] is the length of the longest substring of repeating characters after the i-th query

Example:

If s = "babacc", and we have:

Query 1: Change index 1 to 'b' → String becomes "bbbacc", longest repeating substring is "bbb" with length 3
Query 2: Change index 3 to 'c' → String becomes "bbbccc", longest repeating substring is "ccc" with length 3
And so on...

The problem requires efficiently handling these updates and finding the maximum length of consecutive identical characters after each modification. Since there can be many queries, a naive approach of scanning the entire string after each update would be inefficient, which is why the solution uses a segment tree data structure to maintain and update the required information in O(log n) time per query.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The key insight is that after each character update, we need to quickly find the longest substring of repeating characters in the entire string. A naive approach would scan the entire string after each update, taking O(n) time per query, which becomes O(k * n) total.

We need a way to efficiently maintain information about consecutive characters and update it when a single character changes. This is where a segment tree becomes useful - it can handle point updates and range queries in O(log n) time.

The critical observation is that when we change a single character, it only affects the consecutive character counts in its local region. The rest of the string remains unchanged. So we need a data structure that can:

Update a single position efficiently
Maintain information about consecutive characters in different parts of the string
Combine this information to get the global maximum

For each segment (interval) in our tree, we track three key pieces of information:

lmx: How many consecutive identical characters start from the left boundary of this segment
rmx: How many consecutive identical characters end at the right boundary of this segment
mx: The maximum length of consecutive identical characters within this segment

When we combine two adjacent segments, we need to consider:

The maximum from the left child segment
The maximum from the right child segment
The possibility that the longest sequence spans across both segments (when the rightmost character of the left segment equals the leftmost character of the right segment)

This merging logic allows us to maintain global information about consecutive characters while only updating O(log n) nodes when a character changes. The segment tree structure naturally maintains the hierarchical relationship between intervals, making it perfect for this type of problem where local changes affect global properties.

Learn more about Segment Tree patterns.

Solution Approach

The solution uses a Segment Tree data structure to efficiently handle point updates and maintain information about the longest consecutive repeating characters.

Segment Tree Node Structure

Each node in the segment tree maintains:

l, r: The left and right boundaries of the interval this node represents
lmx: Length of the longest consecutive characters starting from the left boundary
rmx: Length of the longest consecutive characters ending at the right boundary
mx: Maximum length of consecutive characters within this interval

Building the Segment Tree

The build method recursively constructs the tree:

Create a node for interval [l, r]
If it's a leaf node (l == r), initialize all values to 1
Otherwise, recursively build left child for [l, mid] and right child for [mid+1, r]
Call pushup to combine information from children

Pushup Operation

The pushup method is crucial for maintaining correct information after updates. When combining two adjacent segments:

Update prefix maximum (lmx):
- Start with the left child's lmx
- If the left child is entirely uniform (lmx equals its length) AND the boundary characters match, extend with right child's lmx
Update suffix maximum (rmx):
- Start with the right child's rmx
- If the right child is entirely uniform (rmx equals its length) AND the boundary characters match, extend with left child's rmx
Update overall maximum (mx):
- Take the maximum of: left child's mx, right child's mx
- If boundary characters match (s[left.r - 1] == s[right.l - 1]), also consider left.rmx + right.lmx (the sequence spanning both segments)

Modify Operation

To update a character at position x:

Navigate to the appropriate leaf node using binary search logic
Update the character in the string
Call pushup on all affected ancestors going back up the tree

Query Operation

The query always asks for the maximum in the entire range [1, n], which is simply the mx value at the root node.

Time Complexity

Building the tree: O(n)
Each modification: O(log n)
Each query: O(1) (since we query the entire range)
Total for k queries: O(n + k log n)

Implementation Details

The solution uses 1-based indexing for the segment tree nodes, where:

Node u has left child at u << 1 (2u) and right child at u << 1 | 1 (2u + 1)
The root is at index 1
Array size is allocated as 4n to ensure enough space for all nodes

The main solution iterates through each query, performs the modification at the specified index (converting from 0-based to 1-based indexing), and retrieves the maximum consecutive length from the root node.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example with s = "aabba" and process two queries:

Query 1: Change index 2 to 'a'
Query 2: Change index 4 to 'b'

Initial Setup: Build a segment tree for string "aabba" (using 1-based indexing internally).

Initial string: "aabba"
Tree structure (showing [l,r] intervals):
           [1,5]
          /     \
      [1,3]     [4,5]
      /   \      /  \
   [1,2] [3,3] [4,4][5,5]
   /  \
[1,1][2,2]

For each node, we track (lmx, rmx, mx):

Leaf nodes [1,1] through [5,5]: all have (1,1,1)
Node [1,2]: chars 'aa' → (2,2,2) - both are 'a', fully consecutive
Node [3,3]: char 'b' → (1,1,1)
Node [1,3]: chars 'aab' → (2,1,2) - lmx=2 ('aa'), rmx=1 ('b'), mx=2
Node [4,4]: char 'b' → (1,1,1)
Node [5,5]: char 'a' → (1,1,1)
Node [4,5]: chars 'ba' → (1,1,1) - different chars, no consecutive
Root [1,5]: Combining [1,3] and [4,5]:
- Check boundary: s[3]='b', s[4]='b' (they match!)
- lmx = 2 (from left child, not extended since left child not fully uniform)
- rmx = 1 (from right child, not extended since right child not fully uniform)
- mx = max(2, 1, 1+1) = 2 (considering left.mx, right.mx, and left.rmx + right.lmx)

Query 1: Change index 2 to 'a' String becomes "aaaba" (index 2 is position 3 in 1-based indexing)

Modify operation updates node [3,3] and propagates up:

Node [3,3]: still (1,1,1) but now represents 'a'
Node [1,3]: chars 'aaa' → pushup recalculates:
- s[2]='a', s[3]='a' (boundary chars match)
- lmx = 2 + 1 = 3 (left child fully uniform, extend with right)
- rmx = 1 + 2 = 3 (right child fully uniform, extend with left)
- mx = max(2, 1, 2+1) = 3
Root [1,5]: Recalculate with new [1,3]:
- s[3]='a', s[4]='b' (boundary chars don't match)
- lmx = 3 (from left child)
- rmx = 1 (from right child)
- mx = max(3, 1) = 3

Result: Length = 3 (substring "aaa")

Query 2: Change index 4 to 'b' String becomes "aaabb" (index 4 is position 5 in 1-based indexing)

Modify operation updates node [5,5] and propagates up:

Node [5,5]: still (1,1,1) but now represents 'b'
Node [4,5]: chars 'bb' → pushup recalculates:
- s[4]='b', s[5]='b' (boundary chars match)
- lmx = 1 + 1 = 2 (left child fully uniform, extend with right)
- rmx = 1 + 1 = 2 (right child fully uniform, extend with left)
- mx = max(1, 1, 1+1) = 2
Root [1,5]: Recalculate with new [4,5]:
- s[3]='a', s[4]='b' (boundary chars don't match)
- lmx = 3 (from left child)
- rmx = 2 (from right child)
- mx = max(3, 2) = 3

Result: Length = 3 (substring "aaa")

The segment tree efficiently maintains the maximum consecutive length by only updating O(log n) nodes per query, avoiding the need to scan the entire string.

Solution Implementation

1from typing import List, Optional
2
3
4class Node:
5    """Represents a node in the segment tree storing range information."""
6    __slots__ = "l", "r", "lmx", "rmx", "mx"
7  
8    def __init__(self, l: int, r: int):
9        self.l = l        # Left boundary of the range
10        self.r = r        # Right boundary of the range
11        self.lmx = 1      # Maximum consecutive repeating chars from left
12        self.rmx = 1      # Maximum consecutive repeating chars from right
13        self.mx = 1       # Maximum consecutive repeating chars in range
14
15
16class SegmentTree:
17    """Segment tree for efficiently querying and updating longest repeating substring."""
18    __slots__ = "chars", "tree"
19  
20    def __init__(self, s: str):
21        self.chars = list(s)  # Convert string to list for easy modification
22        n = len(s)
23        self.tree: List[Optional[Node]] = [None] * (n * 4)
24        self.build(1, 1, n)
25  
26    def build(self, node_idx: int, left: int, right: int) -> None:
27        """Build the segment tree recursively."""
28        self.tree[node_idx] = Node(left, right)
29      
30        if left == right:
31            # Leaf node - single character
32            return
33      
34        mid = (left + right) // 2
35        # Build left subtree
36        self.build(node_idx << 1, left, mid)
37        # Build right subtree
38        self.build(node_idx << 1 | 1, mid + 1, right)
39        # Update current node based on children
40        self.pushup(node_idx)
41  
42    def query(self, node_idx: int, query_left: int, query_right: int) -> int:
43        """Query the maximum consecutive repeating characters in range [query_left, query_right]."""
44        current_node = self.tree[node_idx]
45      
46        # If current range is completely within query range
47        if current_node.l >= query_left and current_node.r <= query_right:
48            return current_node.mx
49      
50        mid = (current_node.l + current_node.r) // 2
51        result = 0
52      
53        # Query left child if needed
54        if query_left <= mid:
55            result = self.query(node_idx << 1, query_left, query_right)
56      
57        # Query right child if needed
58        if query_right > mid:
59            result = max(result, self.query(node_idx << 1 | 1, query_left, query_right))
60      
61        return result
62  
63    def modify(self, node_idx: int, position: int, new_char: str) -> None:
64        """Modify character at position to new_char (1-indexed position)."""
65        current_node = self.tree[node_idx]
66      
67        if current_node.l == current_node.r:
68            # Leaf node - update the character
69            self.chars[position - 1] = new_char
70            return
71      
72        mid = (current_node.l + current_node.r) // 2
73      
74        if position <= mid:
75            # Update left child
76            self.modify(node_idx << 1, position, new_char)
77        else:
78            # Update right child
79            self.modify(node_idx << 1 | 1, position, new_char)
80      
81        # Update current node based on children
82        self.pushup(node_idx)
83  
84    def pushup(self, node_idx: int) -> None:
85        """Update parent node information based on its children."""
86        root = self.tree[node_idx]
87        left_child = self.tree[node_idx << 1]
88        right_child = self.tree[node_idx << 1 | 1]
89      
90        # Initially inherit values from children
91        root.lmx = left_child.lmx
92        root.rmx = right_child.rmx
93        root.mx = max(left_child.mx, right_child.mx)
94      
95        # Calculate range lengths
96        left_range_size = left_child.r - left_child.l + 1
97        right_range_size = right_child.r - right_child.l + 1
98      
99        # Check if characters at the boundary are the same
100        if self.chars[left_child.r - 1] == self.chars[right_child.l - 1]:
101            # If left child is completely uniform, extend lmx
102            if left_child.lmx == left_range_size:
103                root.lmx += right_child.lmx
104          
105            # If right child is completely uniform, extend rmx
106            if right_child.rmx == right_range_size:
107                root.rmx += left_child.rmx
108          
109            # Update maximum by considering the merge at boundary
110            root.mx = max(root.mx, left_child.rmx + right_child.lmx)
111
112
113class Solution:
114    def longestRepeating(
115        self, s: str, queryCharacters: str, queryIndices: List[int]
116    ) -> List[int]:
117        """
118        Process queries to modify string and return longest repeating substring after each query.
119      
120        Args:
121            s: Initial string
122            queryCharacters: Characters to update at each query
123            queryIndices: 0-indexed positions to update at each query
124          
125        Returns:
126            List of integers representing longest repeating substring after each query
127        """
128        # Initialize segment tree with the string
129        segment_tree = SegmentTree(s)
130        results = []
131      
132        # Process each query
133        for index, char in zip(queryIndices, queryCharacters):
134            # Convert 0-indexed to 1-indexed and modify
135            segment_tree.modify(1, index + 1, char)
136            # Query entire range for maximum consecutive repeating characters
137            max_repeating = segment_tree.query(1, 1, len(s))
138            results.append(max_repeating)
139      
140        return results
141

1/**
2 * Node class representing a segment in the segment tree
3 * Each node stores information about the longest repeating substring in its range
4 */
5class Node {
6    int left, right;           // Range boundaries [left, right]
7    int leftMax, rightMax;      // Maximum repeating length starting from left/ending at right
8    int maxLength;              // Maximum repeating substring length in this range
9  
10    Node(int left, int right) {
11        this.left = left;
12        this.right = right;
13        this.leftMax = 1;      // Initially, each position has at least 1 character
14        this.rightMax = 1;
15        this.maxLength = 1;
16    }
17}
18
19/**
20 * Segment Tree for efficiently querying and updating longest repeating substrings
21 */
22class SegmentTree {
23    private char[] characters;  // The character array (1-indexed internally)
24    private Node[] tree;        // Segment tree nodes
25  
26    /**
27     * Constructor initializes the segment tree with the given string
28     * @param s Character array to build the tree from
29     */
30    public SegmentTree(char[] s) {
31        int n = s.length;
32        this.characters = s;
33        this.tree = new Node[n << 2];  // Allocate 4n space for the tree
34        build(1, 1, n);                // Build tree with 1-based indexing
35    }
36  
37    /**
38     * Recursively builds the segment tree
39     * @param nodeIndex Current node index in the tree
40     * @param rangeLeft Left boundary of current range
41     * @param rangeRight Right boundary of current range
42     */
43    public void build(int nodeIndex, int rangeLeft, int rangeRight) {
44        tree[nodeIndex] = new Node(rangeLeft, rangeRight);
45      
46        // Base case: leaf node
47        if (rangeLeft == rangeRight) {
48            return;
49        }
50      
51        // Recursive case: build left and right subtrees
52        int mid = (rangeLeft + rangeRight) >> 1;
53        int leftChild = nodeIndex << 1;
54        int rightChild = nodeIndex << 1 | 1;
55      
56        build(leftChild, rangeLeft, mid);
57        build(rightChild, mid + 1, rangeRight);
58      
59        // Update current node based on children
60        pushup(nodeIndex);
61    }
62  
63    /**
64     * Modifies a character at the given position
65     * @param nodeIndex Current node index in the tree
66     * @param position Position to modify (1-indexed)
67     * @param newChar New character value
68     */
69    public void modify(int nodeIndex, int position, char newChar) {
70        Node currentNode = tree[nodeIndex];
71      
72        // Base case: reached the target leaf node
73        if (currentNode.left == position && currentNode.right == position) {
74            characters[position - 1] = newChar;  // Convert to 0-indexed
75            return;
76        }
77      
78        // Recursive case: traverse to the appropriate child
79        int mid = (currentNode.left + currentNode.right) >> 1;
80        int leftChild = nodeIndex << 1;
81        int rightChild = nodeIndex << 1 | 1;
82      
83        if (position <= mid) {
84            modify(leftChild, position, newChar);
85        } else {
86            modify(rightChild, position, newChar);
87        }
88      
89        // Update current node after modification
90        pushup(nodeIndex);
91    }
92  
93    /**
94     * Queries the maximum repeating substring length in the given range
95     * @param nodeIndex Current node index in the tree
96     * @param queryLeft Left boundary of query range
97     * @param queryRight Right boundary of query range
98     * @return Maximum repeating substring length in the range
99     */
100    public int query(int nodeIndex, int queryLeft, int queryRight) {
101        Node currentNode = tree[nodeIndex];
102      
103        // Current node's range is completely within query range
104        if (currentNode.left >= queryLeft && currentNode.right <= queryRight) {
105            return currentNode.maxLength;
106        }
107      
108        int mid = (currentNode.left + currentNode.right) >> 1;
109        int result = 0;
110        int leftChild = nodeIndex << 1;
111        int rightChild = nodeIndex << 1 | 1;
112      
113        // Query left subtree if needed
114        if (queryRight <= mid) {
115            result = query(leftChild, queryLeft, queryRight);
116        }
117      
118        // Query right subtree if needed
119        if (queryLeft > mid) {
120            result = Math.max(result, query(rightChild, queryLeft, queryRight));
121        }
122      
123        return result;
124    }
125  
126    /**
127     * Updates parent node based on its children nodes
128     * Merges information from left and right children
129     * @param nodeIndex Index of the node to update
130     */
131    private void pushup(int nodeIndex) {
132        Node parent = tree[nodeIndex];
133        Node leftChild = tree[nodeIndex << 1];
134        Node rightChild = tree[nodeIndex << 1 | 1];
135      
136        // Initial max is the maximum of both children
137        parent.maxLength = Math.max(leftChild.maxLength, rightChild.maxLength);
138      
139        // Initialize parent's left and right max from children
140        parent.leftMax = leftChild.leftMax;
141        parent.rightMax = rightChild.rightMax;
142      
143        // Calculate the full length of left and right ranges
144        int leftRangeLength = leftChild.right - leftChild.left + 1;
145        int rightRangeLength = rightChild.right - rightChild.left + 1;
146      
147        // Check if we can merge across the boundary
148        // If the last character of left child equals first character of right child
149        if (characters[leftChild.right - 1] == characters[rightChild.left - 1]) {
150            // If left child is all same characters, extend parent's leftMax
151            if (leftChild.leftMax == leftRangeLength) {
152                parent.leftMax += rightChild.leftMax;
153            }
154          
155            // If right child is all same characters, extend parent's rightMax
156            if (rightChild.rightMax == rightRangeLength) {
157                parent.rightMax += leftChild.rightMax;
158            }
159          
160            // Update max length considering the merge at boundary
161            parent.maxLength = Math.max(parent.maxLength, 
162                                       leftChild.rightMax + rightChild.leftMax);
163        }
164    }
165}
166
167/**
168 * Solution class for the longest repeating substring problem with updates
169 */
170class Solution {
171    /**
172     * Processes queries to find longest repeating substring after each character update
173     * @param s Original string
174     * @param queryCharacters String of characters to update
175     * @param queryIndices Array of indices where updates occur
176     * @return Array of maximum repeating substring lengths after each update
177     */
178    public int[] longestRepeating(String s, String queryCharacters, int[] queryIndices) {
179        // Initialize segment tree with the string
180        SegmentTree segmentTree = new SegmentTree(s.toCharArray());
181      
182        int numQueries = queryIndices.length;
183        int[] results = new int[numQueries];
184        int stringLength = s.length();
185      
186        // Process each query
187        for (int i = 0; i < numQueries; i++) {
188            // Convert to 1-indexed position for the segment tree
189            int updatePosition = queryIndices[i] + 1;
190            char newCharacter = queryCharacters.charAt(i);
191          
192            // Update the character at the specified position
193            segmentTree.modify(1, updatePosition, newCharacter);
194          
195            // Query the entire string for the maximum repeating substring
196            results[i] = segmentTree.query(1, 1, stringLength);
197        }
198      
199        return results;
200    }
201}
202

1class Node {
2public:
3    int left, right;           // Range boundaries [left, right]
4    int leftMax, rightMax, max; // leftMax: max repeating from left boundary
5                                // rightMax: max repeating from right boundary  
6                                // max: max repeating in this range
7
8    Node(int l, int r)
9        : left(l)
10        , right(r)
11        , leftMax(1)
12        , rightMax(1)
13        , max(1) {}
14};
15
16class SegmentTree {
17private:
18    string str;                 // The string we're tracking
19    vector<Node*> tree;         // Segment tree nodes
20
21    // Build the segment tree recursively
22    void build(int nodeIdx, int left, int right) {
23        tree[nodeIdx] = new Node(left, right);
24      
25        // Leaf node - single character
26        if (left == right) {
27            return;
28        }
29      
30        // Build left and right subtrees
31        int mid = (left + right) >> 1;
32        build(nodeIdx << 1, left, mid);
33        build(nodeIdx << 1 | 1, mid + 1, right);
34      
35        // Update current node based on children
36        pushUp(nodeIdx);
37    }
38
39    // Update parent node based on its children
40    void pushUp(int nodeIdx) {
41        Node* root = tree[nodeIdx];
42        Node* leftChild = tree[nodeIdx << 1];
43        Node* rightChild = tree[nodeIdx << 1 | 1];
44      
45        // Take the maximum from both children
46        root->max = max(leftChild->max, rightChild->max);
47      
48        // Initialize left and right max from children
49        root->leftMax = leftChild->leftMax;
50        root->rightMax = rightChild->rightMax;
51      
52        // Calculate range sizes
53        int leftRangeSize = leftChild->right - leftChild->left + 1;
54        int rightRangeSize = rightChild->right - rightChild->left + 1;
55      
56        // Check if we can merge at the boundary
57        if (str[leftChild->right - 1] == str[rightChild->left - 1]) {
58            // If left child is fully repeating, extend into right child
59            if (leftChild->leftMax == leftRangeSize) {
60                root->leftMax += rightChild->leftMax;
61            }
62          
63            // If right child is fully repeating, extend into left child
64            if (rightChild->rightMax == rightRangeSize) {
65                root->rightMax += leftChild->rightMax;
66            }
67          
68            // Update max considering the merge at boundary
69            root->max = max(root->max, leftChild->rightMax + rightChild->leftMax);
70        }
71    }
72
73public:
74    // Constructor - build segment tree from string
75    SegmentTree(const string& s)
76        : str(s) {
77        int n = s.size();
78        tree.resize(n * 4);     // Allocate space for segment tree
79        build(1, 1, n);         // Build tree with 1-indexed positions
80    }
81
82    // Modify character at position x to value v
83    void modify(int nodeIdx, int position, char value) {
84        // Found the leaf node to update
85        if (tree[nodeIdx]->left == position && tree[nodeIdx]->right == position) {
86            str[position - 1] = value;  // Update string (convert to 0-indexed)
87            return;
88        }
89      
90        // Recursively find the correct leaf
91        int mid = (tree[nodeIdx]->left + tree[nodeIdx]->right) >> 1;
92        if (position <= mid) {
93            modify(nodeIdx << 1, position, value);
94        } else {
95            modify(nodeIdx << 1 | 1, position, value);
96        }
97      
98        // Update current node after modification
99        pushUp(nodeIdx);
100    }
101
102    // Query the maximum repeating substring length in range [left, right]
103    int query(int nodeIdx, int left, int right) {
104        // Current node is completely within query range
105        if (tree[nodeIdx]->left >= left && tree[nodeIdx]->right <= right) {
106            return tree[nodeIdx]->max;
107        }
108      
109        int mid = (tree[nodeIdx]->left + tree[nodeIdx]->right) >> 1;
110        int result = 0;
111      
112        // Query left child only
113        if (right <= mid) {
114            result = query(nodeIdx << 1, left, right);
115        } 
116        // Query right child only
117        else if (left > mid) {
118            result = max(result, query(nodeIdx << 1 | 1, left, right));
119        }
120      
121        return result;
122    }
123};
124
125class Solution {
126public:
127    vector<int> longestRepeating(string s, string queryCharacters, vector<int>& queryIndices) {
128        // Initialize segment tree with the string
129        SegmentTree segTree(s);
130      
131        int numQueries = queryIndices.size();
132        vector<int> result(numQueries);
133        int stringLength = s.size();
134      
135        // Process each query
136        for (int i = 0; i < numQueries; ++i) {
137            int position = queryIndices[i] + 1;  // Convert to 1-indexed
138            char newChar = queryCharacters[i];
139          
140            // Update the character at position
141            segTree.modify(1, position, newChar);
142          
143            // Query the entire string for longest repeating substring
144            result[i] = segTree.query(1, 1, stringLength);
145        }
146      
147        return result;
148    }
149};
150

1// Node structure for segment tree
2interface SegmentNode {
3    left: number;      // Left boundary of the segment
4    right: number;     // Right boundary of the segment
5    leftMax: number;   // Maximum repeating length starting from left boundary
6    rightMax: number;  // Maximum repeating length ending at right boundary
7    max: number;       // Maximum repeating length within this segment
8}
9
10// Global variables for the segment tree
11let charArray: string[];        // Character array representation of the string
12let segmentTree: SegmentNode[]; // Segment tree array
13
14/**
15 * Builds the segment tree recursively
16 * @param nodeIndex - Current node index in the tree
17 * @param leftBound - Left boundary of current segment
18 * @param rightBound - Right boundary of current segment
19 */
20function build(nodeIndex: number, leftBound: number, rightBound: number): void {
21    // Initialize current node with boundaries and default max values of 1
22    segmentTree[nodeIndex] = {
23        left: leftBound,
24        right: rightBound,
25        leftMax: 1,
26        rightMax: 1,
27        max: 1
28    };
29  
30    // Base case: leaf node
31    if (leftBound === rightBound) {
32        return;
33    }
34  
35    // Recursively build left and right subtrees
36    const mid = (leftBound + rightBound) >> 1;
37    const leftChildIndex = nodeIndex << 1;
38    const rightChildIndex = (nodeIndex << 1) | 1;
39  
40    build(leftChildIndex, leftBound, mid);
41    build(rightChildIndex, mid + 1, rightBound);
42  
43    // Update current node based on children
44    pushup(nodeIndex);
45}
46
47/**
48 * Updates parent node information based on its children
49 * @param nodeIndex - Index of the node to update
50 */
51function pushup(nodeIndex: number): void {
52    const currentNode = segmentTree[nodeIndex];
53    const leftChild = segmentTree[nodeIndex << 1];
54    const rightChild = segmentTree[(nodeIndex << 1) | 1];
55  
56    // Update max repeating length from children
57    currentNode.max = Math.max(leftChild.max, rightChild.max);
58  
59    // Initially, inherit boundary max values from children
60    currentNode.leftMax = leftChild.leftMax;
61    currentNode.rightMax = rightChild.rightMax;
62  
63    // Calculate segment lengths
64    const leftSegmentLength = leftChild.right - leftChild.left + 1;
65    const rightSegmentLength = rightChild.right - rightChild.left + 1;
66  
67    // Check if characters at the boundary between left and right segments are the same
68    if (charArray[leftChild.right - 1] === charArray[rightChild.left - 1]) {
69        // If left child is entirely repeating, extend leftMax into right child
70        if (leftChild.leftMax === leftSegmentLength) {
71            currentNode.leftMax += rightChild.leftMax;
72        }
73      
74        // If right child is entirely repeating, extend rightMax into left child
75        if (rightChild.rightMax === rightSegmentLength) {
76            currentNode.rightMax += leftChild.rightMax;
77        }
78      
79        // Update max considering the merge at boundary
80        currentNode.max = Math.max(currentNode.max, leftChild.rightMax + rightChild.leftMax);
81    }
82}
83
84/**
85 * Modifies a character at a specific position
86 * @param nodeIndex - Current node index in the tree
87 * @param position - Position to modify (1-indexed)
88 * @param newChar - New character value
89 */
90function modify(nodeIndex: number, position: number, newChar: string): void {
91    const currentNode = segmentTree[nodeIndex];
92  
93    // Base case: reached the target leaf node
94    if (currentNode.left === position && currentNode.right === position) {
95        charArray[position - 1] = newChar;
96        return;
97    }
98  
99    // Recursively modify in appropriate subtree
100    const mid = (currentNode.left + currentNode.right) >> 1;
101    const leftChildIndex = nodeIndex << 1;
102    const rightChildIndex = (nodeIndex << 1) | 1;
103  
104    if (position <= mid) {
105        modify(leftChildIndex, position, newChar);
106    } else {
107        modify(rightChildIndex, position, newChar);
108    }
109  
110    // Update current node after modification
111    pushup(nodeIndex);
112}
113
114/**
115 * Queries the maximum repeating length in a range
116 * @param nodeIndex - Current node index in the tree
117 * @param queryLeft - Left boundary of query range
118 * @param queryRight - Right boundary of query range
119 * @returns Maximum repeating length in the range
120 */
121function query(nodeIndex: number, queryLeft: number, queryRight: number): number {
122    const currentNode = segmentTree[nodeIndex];
123  
124    // Current segment is completely within query range
125    if (currentNode.left >= queryLeft && currentNode.right <= queryRight) {
126        return currentNode.max;
127    }
128  
129    const mid = (currentNode.left + currentNode.right) >> 1;
130    const leftChildIndex = nodeIndex << 1;
131    const rightChildIndex = (nodeIndex << 1) | 1;
132  
133    let result = 0;
134  
135    // Query is entirely in left subtree
136    if (queryRight <= mid) {
137        result = query(leftChildIndex, queryLeft, queryRight);
138    }
139    // Query is entirely in right subtree
140    else if (queryLeft > mid) {
141        result = Math.max(result, query(rightChildIndex, queryLeft, queryRight));
142    }
143    // Query spans both subtrees
144    else {
145        result = Math.max(
146            query(leftChildIndex, queryLeft, queryRight),
147            query(rightChildIndex, queryLeft, queryRight)
148        );
149    }
150  
151    return result;
152}
153
154/**
155 * Main function to process queries and return longest repeating substring lengths
156 * @param s - Input string
157 * @param queryCharacters - Characters to update at each query
158 * @param queryIndices - Indices to update at each query (0-indexed)
159 * @returns Array of maximum repeating lengths after each query
160 */
161function longestRepeating(s: string, queryCharacters: string, queryIndices: number[]): number[] {
162    // Initialize global variables
163    charArray = s.split('');
164    const stringLength = s.length;
165    segmentTree = Array(stringLength * 4)
166        .fill(null)
167        .map(() => ({ left: 0, right: 0, leftMax: 1, rightMax: 1, max: 1 }));
168  
169    // Build the segment tree
170    build(1, 1, stringLength);
171  
172    // Process queries
173    const queryCount = queryIndices.length;
174    const results: number[] = new Array(queryCount);
175  
176    for (let i = 0; i < queryCount; i++) {
177        // Convert to 1-indexed position
178        const updatePosition = queryIndices[i] + 1;
179        const updateChar = queryCharacters[i];
180      
181        // Modify the character at the specified position
182        modify(1, updatePosition, updateChar);
183      
184        // Query the entire range for maximum repeating length
185        results[i] = query(1, 1, stringLength);
186    }
187  
188    return results;
189}
190

Time and Space Complexity

Time Complexity: O((n + q) × log n) where n is the length of string s and q is the number of queries.

Building the segment tree: The build method is called once and visits each node in the tree exactly once. Since there are O(n) nodes in total (approximately 4n nodes for a segment tree), and each node performs O(1) work except for the pushup operation which is also O(1), the build time is O(n).
Query operation: Each query call traverses at most O(log n) levels of the tree (the height of the tree), performing O(1) work at each level. Since we perform q queries, the total query time is O(q × log n).
Modify operation: Each modify call traverses from root to leaf, which is O(log n) levels, and then calls pushup on the way back up, visiting O(log n) nodes. Each pushup operation is O(1). Since we perform q modifications, the total modification time is O(q × log n).
Total time complexity: O(n + q × log n). When q is proportional to n, this becomes O(n × log n), which matches the reference answer.

Space Complexity: O(n)

Segment tree storage: The tree array tr has size 4n, storing Node objects. Each Node has constant space (5 integer attributes), so the tree requires O(n) space.
String storage: The string s is converted to a list of characters, requiring O(n) space.
Output array: The answer array stores q integers, requiring O(q) space.
Total space complexity: O(n + q). When q is proportional to n, this becomes O(n).

Note: The reference answer states O(n × log n) for space complexity, but the actual implementation uses an array-based segment tree with 4n nodes, which is O(n) space, not O(n × log n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Boundary Character Comparison in Pushup

One of the most common mistakes is incorrectly handling the boundary character comparison when merging two segments. The critical issue is using wrong indices when checking if adjacent segments can be merged.

Pitfall Code:

# WRONG: Using 0-based index directly
if self.chars[left_child.r] == self.chars[right_child.l]:
    # This will cause index out of bounds or compare wrong characters

Correct Code:

# CORRECT: Convert to 0-based index by subtracting 1
if self.chars[left_child.r - 1] == self.chars[right_child.l - 1]:
    # Properly compares the last char of left segment with first char of right segment

2. Not Handling Single Character Updates Properly

Another pitfall is forgetting that when we update a character, it affects not just the containing segment but all ancestor segments up to the root. Some implementations might update only the leaf node without propagating changes upward.

Pitfall Implementation:

def modify(self, node_idx: int, position: int, new_char: str) -> None:
    current_node = self.tree[node_idx]
  
    if current_node.l == current_node.r:
        self.chars[position - 1] = new_char
        return  # WRONG: Returns without updating ancestors
  
    # Recursive calls without pushup
    mid = (current_node.l + current_node.r) // 2
    if position <= mid:
        self.modify(node_idx << 1, position, new_char)
    else:
        self.modify(node_idx << 1 | 1, position, new_char)
    # MISSING: self.pushup(node_idx)

3. Incorrect Calculation of Merged Sequence Length

When two segments can be merged at their boundary, the total length of the merged sequence must consider both the suffix of the left segment and the prefix of the right segment.

Pitfall Code:

# WRONG: Only considering one side or using wrong values
root.mx = max(root.mx, left_child.mx + right_child.mx)  # Incorrect!

Correct Code:

# CORRECT: Use suffix of left (rmx) and prefix of right (lmx)
root.mx = max(root.mx, left_child.rmx + right_child.lmx)

4. Index Conversion Between 0-based and 1-based

The segment tree uses 1-based indexing internally, but Python strings use 0-based indexing. Mixing these up is a frequent source of errors.

Common Mistakes:

# WRONG: Forgetting to convert when accessing the character array
char_at_position = self.chars[position]  # Should be position - 1

# WRONG: Not converting query indices in the main solution
segment_tree.modify(1, index, char)  # Should be index + 1

5. Not Checking Complete Uniformity Before Extension

When updating lmx and rmx in pushup, we must verify that a child segment is completely uniform before extending the parent's prefix/suffix.

Pitfall Code:

# WRONG: Extending without checking if child is completely uniform
if self.chars[left_child.r - 1] == self.chars[right_child.l - 1]:
    root.lmx = left_child.lmx + right_child.lmx  # Always extends!

Correct Code:

# CORRECT: Only extend if the entire left child is uniform
if self.chars[left_child.r - 1] == self.chars[right_child.l - 1]:
    if left_child.lmx == left_child.r - left_child.l + 1:  # Check uniformity
        root.lmx = left_child.lmx + right_child.lmx

Solution to Avoid These Pitfalls:

Always draw out index mappings between your segment tree (1-based) and array (0-based)
Test with small examples where you can manually verify the pushup calculations
Add assertions during development to catch index errors early
Visualize the merge cases on paper before coding the pushup logic
Use consistent naming for indices to avoid confusion (e.g., always suffix with _0based or _1based during development)

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

2213. Longest Substring of One Repeating Character

Problem Description

Intuition

Solution Approach

Segment Tree Node Structure

Building the Segment Tree

Pushup Operation

Modify Operation

Query Operation

Time Complexity

Implementation Details

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Example Walkthrough

Solution Implementation

Time and Space Complexity

Common Pitfalls

1. Boundary Character Comparison in Pushup

2. Not Handling Single Character Updates Properly

3. Incorrect Calculation of Merged Sequence Length

4. Index Conversion Between 0-based and 1-based

5. Not Checking Complete Uniformity Before Extension

Solution to Avoid These Pitfalls:

Recommended Readings