2213. Longest Substring of One Repeating Character

HardSegment TreeArrayStringOrdered Set
Leetcode Link

Problem Description

You are provided with a string s that is indexed starting from zero. Additionally, you are given a string queryCharacters with a length k and an array of integers queryIndices also of length k. These strings and the array represent a series of k queries.

Each query updates the character in the string s at the index specified in queryIndices[i] with the character from queryCharacters[i].

The goal is to find out the length of the longest substring in s that consists of a single repeating character after each query. The answer to this should be returned as an array lengths, where lengths[i] reflects the longest homogeneous substring length after performing the i-th query.

Intuition

To efficiently handle multiple queries and update operations on the string, we utilize a Segment Tree — a powerful data structure suited for range query and update operations.

The solution is centered around maintaining the longest homogeneous substring within each segment or node. Our segment tree will consist of nodes that store several important pieces of information about the segment:

  • The left and right bounds of the segment.
  • The longest homogeneous substring that strictly begins at the left bounds (lmx).
  • The longest homogeneous substring that strictly ends at the right bounds (rmx).
  • The overall longest homogeneous substring within the segment (mx).
  • The total size or length of the segment (size).
  • The leftmost and rightmost characters within the segment (lc and rc).

When updating a character within our string, we'll modify the segment tree node that corresponds to that character's index, then update all subsequent parent nodes to reflect this change. The pushup function is used to update the parent node based on the values of its left and right child nodes.

Finally, with each query after updating, we perform a query operation on the segment tree to find the longest homogeneous substring's length after the update. The maximal length found will then be appended to our ans array, which will be returned at the end.

This approach is particularly efficient because segment trees allow us to perform update and query operations in O(log n) time, where n is the number of characters in the string s. This time complexity is much better than that of naive methods, such as iterating through the string for each query, which would result in a time complexity of O(n * k).

Learn more about Segment Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Solution Approach

The given solution uses a Segment Tree to efficiently find the longest repeating substring within s for each query. Here's how it works, with reference to the code above:

Segment Tree Node Definition

  • Each node in the tree is represented by the Node class. This node stores all necessary information, including the bounds of the segment (l, r), the maximum lengths (lmx, rmx, mx), and the leading and trailing characters (lc, rc).

Segment Tree Construction

  • The SegmentTree class is initialized with the input string. The build method is recursively called to build the segment tree by splitting the string into single-character segments and then merging them, combining segment properties using the pushup method.

Update Operation

  • modify method updates the tree. The character at x is updated to v. If the updated index lands in the left subtree, that subtree is modified; if it's in the right subtree, that subtree is modified instead. After the modifications, the pushup method updates the parent nodes recursively.

Query Operation

  • query method is used after each update. It retrieves the information from a specific segment, or merges information from two child segments if the query range spans more than one segment. The pushup method assists in merging information from the nodes.

Helper Functions

  • The _pushup method is a critical part of this implementation: it takes the maximum lengths of individual segments and left and right characters, and updates the parent node's information based on its children. This includes calculating the new maximum homogeneous substring lengths if the right character of the left child segment and the left character of the right child segment are identical.
  • The pushup method is used for managing the propagation of updates to the segment tree nodes after changes have been made or during tree building.

Solution Method

  • In longestRepeating, the algorithm constructs the segment tree with the initial string and then iterates over each query.
  • For every query, the modify method of the segment tree is called to apply the character update at the specified index.
  • After each update, the algorithm calls the query method for the entire range to find the longest repeating substring's new length.
  • The result from the query is appended to a list ans that is returned once all queries are processed.

By using the segment tree, we efficiently update and query the tree. Each operation in the tree has an average runtime complexity of O(log n), making it fast enough to handle a large number of queries on sizable strings, which would be impractical to do with a simpler, brute-force approach.

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

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Example Walkthrough

Consider a string s = "aabb" and the query updates given by queryCharacters = "ba" and queryIndices = [1, 2]. We need to process the queries and determine the length of the longest homogeneous substring after each update.

  • Initial string: s = "aabb"
  • Initial longest homogeneous substring: "aa" with length 2.

First query: Update the character at index 1 with 'b'.

  • Updated string: s = "abbb"
  • After the update, we update the segment tree and perform a query operation over the entire range of the string.
  • Now, the longest homogeneous substring is "bbb" with length 3. We append this length to our answer array.

Second query: Update the character at index 2 with 'a'.

  • Updated string: s = "abab"
  • We perform the segment tree update and query operations again.
  • The longest homogeneous substrings are "a", "b", with each substring length 1 after the update. Thus, the longest length remains 1. We append this length to our answer array.

Hence the answer array after processing both queries is [3, 1].

  1. Segment Tree Construction: We build a segment tree from the initial string 'aabb'. Each leaf node represents a single character, and each parent node represents a combination of its children. For instance, the first leaf node is ['a', 'a', 2, 2, 2, 2], where lc = rc = 'a' and lmx = rmx = mx = size = 2 as both characters are 'a'. Similarly, all leaf and parent nodes are initialized.

  2. First Update Operation: When we modify index 1 to 'b', we locate the corresponding leaf node and modify its value, then use the pushup function to update the parent nodes. After the update, the root node reflects the longest homogeneous substring 'bbb' which has length 3.

  3. Query Operation: We perform a query on the entire range and find that the maximum homogeneous substring length is 3.

  4. Second Update Operation: When we modify index 2 to 'a', again we update the corresponding leaf node and the parent nodes. The longest homogeneous substring lengths within any node are now 1 as 'a' and 'b' alternate in the string.

  5. Query Operation: Another range query on the entire string returns the maximum homogeneous substring length, which is now 1.

The answer array will be filled with values [3, 1] through the range of queries, representing the lengths of the longest homogeneous substring after each update, effectively demonstrating the solution approach.

Solution Implementation

1class Node:
2    def __init__(self):
3        self.left = 0
4        self.right = 0
5        self.left_max = 0
6        self.right_max = 0
7        self.max = 0
8        self.size = 0
9        self.left_child = None
10        self.right_child = None
11
12
13# Constant N for max array size
14N = 100010
15# Initialize array for segment tree
16segment_tree = [Node() for _ in range(N << 2)]
17
18
19class SegmentTree:
20    def __init__(self, s):
21        self.string = s
22        self.length = len(s)
23        self.build(1, 1, self.length)
24
25    def build(self, u, l, r):
26        segment_tree[u].left = l
27        segment_tree[u].right = r
28        # If leaf node, initialize values
29        if l == r:
30            segment_tree[u].left_max = segment_tree[u].right_max = segment_tree[u].max = segment_tree[u].size = 1
31            segment_tree[u].left_child = segment_tree[u].right_child = self.string[l - 1]
32            return
33        mid = (l + r) >> 1
34        self.build(u << 1, l, mid)
35        self.build(u << 1 | 1, mid + 1, r)
36        self.pushup(u)
37
38    def modify(self, u, x, v):
39        # Modify the value of the node in segment tree
40        if segment_tree[u].left == x and segment_tree[u].right == x:
41            segment_tree[u].left_child = segment_tree[u].right_child = v
42            return
43        mid = (segment_tree[u].left + segment_tree[u].right) >> 1
44        if x <= mid:
45            self.modify(u << 1, x, v)
46        else:
47            self.modify(u << 1 | 1, x, v)
48        self.pushup(u)
49
50    def query(self, u, l, r):
51        # Query the segment tree 
52        if segment_tree[u].left >= l and segment_tree[u].right <= r:
53            return segment_tree[u]
54        mid = (segment_tree[u].left + segment_tree[u].right) >> 1
55        if r <= mid:
56            return self.query(u << 1, l, r)
57        if l > mid:
58            return self.query(u << 1 | 1, l, r)
59        left_node, right_node = self.query(u << 1, l, r), self.query(u << 1 | 1, l, r)
60        temp_node = Node()
61        self._pushup(temp_node, left_node, right_node)
62        return temp_node
63
64    def _pushup(self, root, left, right):
65        root.left_child, root.right_child = left.left_child, right.right_child
66        root.size = left.size + right.size
67
68        root.max = max(left.max, right.max)
69        root.left_max, root.right_max = left.left_max, right.right_max
70
71        # Adjusting the maximum sequence if needed
72        if left.right_child == right.left_child:
73            if left.left_max == left.size:
74                root.left_max += right.left_max
75            if right.right_max == right.size:
76                root.right_max += left.right_max
77            root.max = max(root.max, left.right_max + right.left_max)
78
79    def pushup(self, u):
80        # Function that updates the values in the segment tree from its children
81        self._pushup(segment_tree[u], segment_tree[u << 1], segment_tree[u << 1 | 1])
82
83
84class Solution:
85    def longestRepeating(self, s: str, query_characters: str, query_indices: list) -> list:
86        tree = SegmentTree(s)
87        results = []
88        for i, char in enumerate(query_characters):
89            index = query_indices[i] + 1
90            tree.modify(1, index, char)
91            results.append(tree.query(1, 1, len(s)).max)
92        return results
93
1class Node {
2    int left;
3    int right;
4    int size;
5    int leftMax;
6    int rightMax;
7    int max;
8    char leftChar;
9    char rightChar;
10}
11
12class SegmentTree {
13    private String s;
14    private Node[] tree;
15
16    public SegmentTree(String s) {
17        int n = s.length();
18        this.s = s;
19        tree = new Node[n << 2];
20        for (int i = 0; i < tree.length; ++i) {
21            tree[i] = new Node();
22        }
23        build(1, 1, n);
24    }
25
26    // Build the segment tree
27    public void build(int nodeIndex, int left, int right) {
28        tree[nodeIndex].left = left;
29        tree[nodeIndex].right = right;
30        if (left == right) { // Leaf node
31            tree[nodeIndex].leftMax = 1;
32            tree[nodeIndex].rightMax = 1;
33            tree[nodeIndex].max = 1;
34            tree[nodeIndex].size = 1;
35            tree[nodeIndex].leftChar = s.charAt(left - 1);
36            tree[nodeIndex].rightChar = s.charAt(left - 1);
37            return;
38        }
39        int mid = (left + right) >> 1;
40        build(nodeIndex << 1, left, mid); // Build left subtree
41        build(nodeIndex << 1 | 1, mid + 1, right); // Build right subtree
42        pushUp(nodeIndex); // Merge left and right subtrees
43    }
44
45    // Modify a single character in the string
46    void modify(int nodeIndex, int position, char value) {
47        if (tree[nodeIndex].left == position && tree[nodeIndex].right == position) { // Leaf node
48            tree[nodeIndex].leftChar = value;
49            tree[nodeIndex].rightChar = value;
50            return;
51        }
52        int mid = (tree[nodeIndex].left + tree[nodeIndex].right) >> 1;
53        if (position <= mid) {
54            modify(nodeIndex << 1, position, value); // Modify left subtree
55        } else {
56            modify(nodeIndex << 1 | 1, position, value); // Modify right subtree
57        }
58        pushUp(nodeIndex); // Push up the changes
59    }
60
61    // Query the segment tree for the longest repeating substring
62    Node query(int nodeIndex, int left, int right) {
63        if (tree[nodeIndex].left >= left && tree[nodeIndex].right <= right) {
64            return tree[nodeIndex];
65        }
66        int mid = (tree[nodeIndex].left + tree[nodeIndex].right) >> 1;
67        if (right <= mid) {
68            return query(nodeIndex << 1, left, right); // Query left subtree
69        }
70        if (left > mid) {
71            return query(nodeIndex << 1 | 1, left, right); // Query right subtree
72        }
73        Node result = new Node();
74        Node leftResult = query(nodeIndex << 1, left, right);
75        Node rightResult = query(nodeIndex << 1 | 1, left, right);
76        pushUp(result, leftResult, rightResult); // Merge results
77        return result;
78    }
79
80    // Push up from children to parent node
81    void pushUp(Node root, Node leftChild, Node rightChild) {
82        root.leftChar = leftChild.leftChar;
83        root.rightChar = rightChild.rightChar;
84        root.size = leftChild.size + rightChild.size;
85
86        root.max = Math.max(leftChild.max, rightChild.max);
87        root.leftMax = leftChild.leftMax;
88        root.rightMax = rightChild.rightMax;
89
90        // Consider the case when adjacent segments can be merged into a longer repeating substring
91        if (leftChild.rightChar == rightChild.leftChar) {
92            if (leftChild.leftMax == leftChild.size) {
93                root.leftMax += rightChild.leftMax;
94            }
95            if (rightChild.rightMax == rightChild.size) {
96                root.rightMax += leftChild.rightMax;
97            }
98            root.max = Math.max(root.max, leftChild.rightMax + rightChild.leftMax);
99        }
100    }
101
102    // Helper method to perform a push-up operation on the main tree nodes
103    void pushUp(int nodeIndex) {
104        pushUp(tree[nodeIndex], tree[nodeIndex << 1], tree[nodeIndex << 1 | 1]);
105    }
106}
107
108class Solution {
109    // Find the length of the longest repeating character substring after each query operation
110    public int[] longestRepeating(String s, String queryCharacters, int[] queryIndices) {
111        SegmentTree tree = new SegmentTree(s);
112        int queryLength = queryCharacters.length();
113        int[] answer = new int[queryLength];
114        for (int i = 0; i < queryLength; ++i) {
115            int index = queryIndices[i] + 1;
116            char character = queryCharacters.charAt(i);
117            tree.modify(1, index, character); // Perform the modification in the segment tree
118            answer[i] = tree.query(1, 1, s.length()).max; // Query the longest repeating substring
119        }
120        return answer;
121    }
122}
123
1#include <vector>
2#include <string>
3#include <algorithm>
4using namespace std;
5
6// Node of the segment tree to hold information about a substring
7class Node {
8public:
9    int left, right, size, longestPrefix, longestSuffix, maxLength;
10    char leftChar, rightChar;
11};
12
13// Segment tree to manage substring operations efficiently
14class SegmentTree {
15private:
16    string str;               // The string on which the segment tree is built
17    vector<Node*> tree;       // Stores the nodes of the segment tree
18
19    // Builds the segment tree recursively
20    void build(int nodeIndex, int left, int right) {
21        // Initialize the bounds of the node
22        tree[nodeIndex]->left = left;
23        tree[nodeIndex]->right = right;
24      
25        if (left == right) {  // If it's a leaf node, initialize its values based on the string character
26            tree[nodeIndex]->longestPrefix = tree[nodeIndex]->longestSuffix =
27            tree[nodeIndex]->maxLength = tree[nodeIndex]->size = 1;
28            tree[nodeIndex]->leftChar = tree[nodeIndex]->rightChar = str[left - 1];
29            return;
30        }
31      
32        int mid = (left + right) >> 1;  // Get the middle index for splitting
33        build(nodeIndex << 1, left, mid);  // Recursive build for left child
34        build(nodeIndex << 1 | 1, mid + 1, right);  // Recursive build for right child
35        pushUp(nodeIndex);  // Update the current node values based on children
36    }
37
38    // Propagates the values of child nodes to the parent node
39    void pushUp(int u) {
40        Node* root = tree[u];
41        Node* left = tree[u << 1];
42        Node* right = tree[u << 1 | 1];
43      
44        root->leftChar = left->leftChar;
45        root->rightChar = right->rightChar;
46        root->size = left->size + right->size;
47      
48        root->maxLength = max(left->maxLength, right->maxLength);
49        root->longestPrefix = left->longestPrefix;
50        root->longestSuffix = right->longestSuffix;
51      
52        if (left->rightChar == right->leftChar) {
53            if (left->longestPrefix == left->size) 
54                root->longestPrefix += right->longestPrefix;
55            if (right->longestSuffix == right->size) 
56                root->longestSuffix += left->longestSuffix;
57            root->maxLength = max(root->maxLength, left->longestSuffix + right->longestPrefix);
58        }
59    }
60
61public:
62    // Constructor for the segment tree based on the provided string
63    SegmentTree(string& s) : str(s) {
64        int n = s.size();
65        tree.resize(n << 2);
66        for (int i = 0; i < (int)tree.size(); ++i) 
67            tree[i] = new Node();
68        build(1, 1, n);
69    }
70
71    // Modifies a character in the string and updates the tree accordingly
72    void modify(int nodeIndex, int position, char value) {
73        if (tree[nodeIndex]->left == position && tree[nodeIndex]->right == position) {
74            tree[nodeIndex]->leftChar = tree[nodeIndex]->rightChar = value;
75            return;
76        }
77      
78        int mid = (tree[nodeIndex]->left + tree[nodeIndex]->right) >> 1;
79        if (position <= mid)
80            modify(nodeIndex << 1, position, value);
81        else
82            modify(nodeIndex << 1 | 1, position, value);
83        pushUp(nodeIndex);
84    }
85
86    // Queries the segment tree to find the node that matches the given range
87    Node* query(int nodeIndex, int left, int right) {
88        if (tree[nodeIndex]->left >= left && tree[nodeIndex]->right <= right) return tree[nodeIndex];
89      
90        int mid = (tree[nodeIndex]->left + tree[nodeIndex]->right) >> 1;
91        if (right <= mid) return query(nodeIndex << 1, left, right);
92        if (left > mid) return query(nodeIndex << 1 | 1, left, right);
93      
94        Node* answer = new Node();
95        Node* leftNode = query(nodeIndex << 1, left, right);
96        Node* rightNode = query(nodeIndex << 1 | 1, left, right);
97      
98        // Create and return the parent node by combining left and right nodes
99        Node* root = new Node();
100        root->leftChar = leftNode->leftChar;
101        root->rightChar = rightNode->rightChar;
102        root->size = leftNode->size + rightNode->size;
103      
104        root->maxLength = max(leftNode->maxLength, rightNode->maxLength);
105        root->longestPrefix = leftNode->longestPrefix;
106        root->longestSuffix = rightNode->longestSuffix;
107
108        if (leftNode->rightChar == rightNode->leftChar) {
109            if (leftNode->longestPrefix == leftNode->size) 
110                root->longestPrefix += rightNode->longestPrefix;
111            if (rightNode->longestSuffix == rightNode->size) 
112                root->longestSuffix += leftNode->longestSuffix;
113            root->maxLength = max(root->maxLength, leftNode->longestSuffix + rightNode->longestPrefix);
114        }
115        return root;
116    }
117};
118
119// The main solution class that uses the SegmentTree to solve the problem
120class Solution {
121public:
122    vector<int> longestRepeating(string s, string queryCharacters, vector<int>& queryIndices) {
123        SegmentTree* tree = new SegmentTree(s);
124        int queryCount = queryCharacters.size();
125        vector<int> answers(queryCount);
126      
127        for (int i = 0; i < queryCount; ++i) {
128            int index = queryIndices[i] + 1;
129            tree->modify(1, index, queryCharacters[i]);
130            answers[i] = tree->query(1, 1, s.size())->maxLength;
131        }
132      
133        return answers;
134    }
135};
136
1type Node = {
2    left: number;
3    right: number;
4    size: number;
5    longestPrefix: number;
6    longestSuffix: number;
7    maxLength: number;
8    leftChar: string;
9    rightChar: string;
10};
11
12// The string on which the segment tree is built
13let str: string; 
14
15// Stores the nodes of the segment tree
16let tree: Array<Node | null>;
17
18// Builds the segment tree recursively
19function build(nodeIndex: number, left: number, right: number): void {
20    // Initialize the bounds of the node
21    tree[nodeIndex] = {
22        left,
23        right,
24        size: 0,
25        longestPrefix: 0,
26        longestSuffix: 0,
27        maxLength: 0,
28        leftChar: '',
29        rightChar: ''
30    };
31
32    if (left === right) {
33        // If it's a leaf node, initialize its values based on the string character
34        const char = str[left - 1];
35        tree[nodeIndex].longestPrefix = 1;
36        tree[nodeIndex].longestSuffix = 1;
37        tree[nodeIndex].maxLength = 1;
38        tree[nodeIndex].size = 1;
39        tree[nodeIndex].leftChar = char;
40        tree[nodeIndex].rightChar = char;
41        return;
42    }
43
44    const mid = Math.floor((left + right) / 2);
45    build(nodeIndex * 2, left, mid); // Recursive build for left child
46    build(nodeIndex * 2 + 1, mid + 1, right); // Recursive build for right child
47    pushUp(nodeIndex); // Update the current node values based on children
48}
49
50// Propagates the values of child nodes to the parent node
51function pushUp(nodeIndex: number): void {
52    const root = tree[nodeIndex];
53    const leftNode = tree[nodeIndex * 2];
54    const rightNode = tree[nodeIndex * 2 + 1];
55
56    if (root && leftNode && rightNode) {
57        root.leftChar = leftNode.leftChar;
58        root.rightChar = rightNode.rightChar;
59        root.size = leftNode.size + rightNode.size;
60
61        root.maxLength = Math.max(leftNode.maxLength, rightNode.maxLength);
62        root.longestPrefix = leftNode.longestPrefix;
63        root.longestSuffix = rightNode.longestSuffix;
64
65        if (leftNode.rightChar === rightNode.leftChar) {
66            if (leftNode.longestPrefix === leftNode.size) {
67                root.longestPrefix += rightNode.longestPrefix;
68            }
69            if (rightNode.longestSuffix === rightNode.size) {
70                root.longestSuffix += leftNode.longestSuffix;
71            }
72            root.maxLength = Math.max(root.maxLength, leftNode.longestSuffix + rightNode.longestPrefix);
73        }
74    }
75}
76
77// Modifies a character in the string and updates the tree accordingly
78function modify(nodeIndex: number, position: number, value: string): void {
79    const node = tree[nodeIndex];
80    if (node && node.left === position && node.right === position) {
81        node.leftChar = value;
82        node.rightChar = value;
83        return;
84    }
85
86    const mid = Math.floor((node.left + node.right) / 2);
87    if (position <= mid) {
88        modify(nodeIndex * 2, position, value);
89    } else {
90        modify(nodeIndex * 2 + 1, position, value);
91    }
92    pushUp(nodeIndex);
93}
94
95// Queries the segment tree to find the maximum length of repeating characters in the given range
96function query(nodeIndex: number, left: number, right: number): Node {
97    const node = tree[nodeIndex];
98
99    if (!node) throw new Error("Query node is not available");
100
101    if (node.left >= left && node.right <= right) return node;
102
103    const mid = Math.floor((node.left + node.right) / 2);
104    if (right <= mid) {
105        return query(nodeIndex * 2, left, right);
106    } else if (left > mid) {
107        return query(nodeIndex * 2 + 1, left, right);
108    } else {
109        const leftNode = query(nodeIndex * 2, left, mid);
110        const rightNode = query(nodeIndex * 2 + 1, mid + 1, right);
111
112        const answer: Node = {
113            left: 0,
114            right: 0,
115            size: leftNode.size + rightNode.size,
116            longestPrefix: leftNode.longestPrefix,
117            longestSuffix: rightNode.longestSuffix,
118            maxLength: Math.max(leftNode.maxLength, rightNode.maxLength),
119            leftChar: leftNode.leftChar,
120            rightChar: rightNode.rightChar,
121        };        
122
123        if (leftNode.rightChar === rightNode.leftChar) {
124            if (leftNode.longestPrefix === leftNode.size) {
125                answer.longestPrefix += rightNode.longestPrefix;
126            }
127            if (rightNode.longestSuffix === rightNode.size) {
128                answer.longestSuffix += leftNode.longestSuffix;
129            }
130            answer.maxLength = Math.max(answer.maxLength, leftNode.longestSuffix + rightNode.longestPrefix);
131        }
132
133        return answer;
134    }
135}
136
137// Initializes segment tree and performs queries to get the maximum length of repeating characters after each modification
138function longestRepeating(s: string, queryCharacters: string, queryIndices: number[]): number[] {
139    str = s;
140    const n = s.length;
141    tree = new Array<Node | null>(n * 4);
142    build(1, 1, n);
143
144    const queryCount = queryCharacters.length;
145    const answers = new Array<number>(queryCount);
146
147    for (let i = 0; i < queryCount; ++i) {
148        const index = queryIndices[i] + 1;
149        modify(1, index, queryCharacters[i]);
150        answers[i] = query(1, 1, n).maxLength;
151    }
152
153    return answers;
154}
155
Not Sure What to Study? Take the 2-min Quiz：

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Time and Space Complexity

The provided code defines a Segment Tree to maintain different properties of a string of characters to solve the problem of computing the longest repeating character after a series of mutations are performed.

Time Complexity:

  1. SegmentTree.build:

    • This function constructs the segment tree. The time complexity of building a segment tree is O(n), where n is the number of elements in the string s.

  2. SegmentTree.modify:

    • In the worst-case scenario, modify operates on a path from the root to a leaf node, with a complexity of O(log n) for each operation.

  3. SegmentTree.query:

    • Similarly, a query traverses from the root to leaves and possibly spans across different branches. The time complexity for each query operation is also O(log n).

  4. The Solution.longestRepeating function calls modify once for each query character and query once, resulting in a complexity of O(k log n) for all requests, where k is the number of queries.

Considering m as the length of the input s and k as the number of queries, the total time complexity of this function is O(m + k log m).

Space Complexity:

  1. N << 2 storage for nodes in the tr array represents a static allocation that depends on a predefined value N. Since each node in a segment tree only requires a constant amount of space and the total number of nodes in a perfectly balanced binary tree is 2n - 1, we can approximate the space complexity of the tree array as O(4N), which simplifies to O(N).

  2. Each operation does not use additional space proportional to the size of the input, except for the output list and some constant space for temporary variables in the modify, query, and pushup functions.

Therefore, the space complexity of the overall Segment Tree structure is O(N) and the space complexity of the solution execution is O(m) for the output list, where m is the length of the result list which is the same as the number of queries k. Thus, we can say the total space complexity is O(N + m) or O(N + k).

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

Fast Track Your Learning with Our Quick Skills Quiz:

How many times is a tree node visited in a depth first search?

Recommended Readings

Segment Tree

Segment Tree Faster Range Queries For this article we want to introduce the idea of a Segment Tree Segment Trees allow us to quickly perform range queries as well as range updates Suppose we have an array and we want to know the sum of a particular range of numbers as well

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫