Longest Substring of One Repeating Character solution and explanation
4 more videos on this problem
Leetcode Weekly 285 | 2213. Longest Substring of One Repeating CharactercodingMohan · 25:07 · 2K views
Longest Substring Of One Repeating Character || LeetCode Weekly Contest 285 || Problem DCompetitive Coding - Newton School · 17:50 · 1K views
【每日一题】LeetCode 2213. Longest Substring of One Repeating CharacterHuifeng Guan · 34:58 · 638 views
2213. Longest Substring of One Repeating Character (Leetcode Hard)Programming Live with Larry · 1:20:57 · 474 views
LeetCode 2213: Longest Substring of One Repeating CharacterAlitaCode · 31:46 · 31 views
The problem
You are given a 0-indexed string s. You are also given a 0-indexed string queryCharacters of length k and a 0-indexed array of integer indices queryIndices of length k, both of which are used to describe k queries.
The ith query updates the character in s at index queryIndices[i] to the character queryCharacters[i].
Return an array lengths of length k where lengths[i] is the length of the longest substring of s consisting of only one repeating character after the ith query is performed.
Example 1:
Input: s = "babacc", queryCharacters = "bcb", queryIndices = [1,3,3] Output: [3,3,4] Explanation: - 1st query updates s = "bbbacc". The longest substring consisting of one repeating character is "bbb" with length 3. - 2nd query updates s = "bbbccc". The longest substring consisting of one repeating character can be "bbb" or "ccc" with length 3. - 3rd query updates s = "bbbbcc". The longest substring consisting of one repeating character is "bbbb" with length 4. Thus, we return [3,3,4].
Example 2:
Input: s = "abyzz", queryCharacters = "aa", queryIndices = [2,1] Output: [2,3] Explanation: - 1st query updates s = "abazz". The longest substring consisting of one repeating character is "zz" with length 2. - 2nd query updates s = "aaazz". The longest substring consisting of one repeating character is "aaa" with length 3. Thus, we return [2,3].
Constraints:
1 <= s.length <= 105sconsists of lowercase English letters.k == queryCharacters.length == queryIndices.length1 <= k <= 105queryCharactersconsists of lowercase English letters.0 <= queryIndices[i] < s.length
Approach overview
Problem Overview: You start with a string s. Each query updates a single index with a new character. After every update, return the length of the longest substring consisting of only one repeating character. The challenge is efficiently recomputing this value after each modification.
Approach 1: Naive Approach with Recalculation (O(n) per query, O(1) space)
After each character update, recompute the longest repeating substring by scanning the entire string. Iterate through s while tracking the length of the current run of identical characters and the global maximum. Whenever the character changes, reset the run counter and continue. This approach uses only a few variables and works for any string size, but every query forces a full pass over the array. If there are q updates and the string length is n, the total complexity becomes O(n * q). It’s simple and reliable but too slow when both n and q are large.
Approach 2: Optimized Sliding Window Style Scan (O(n) per query, O(1) space)
A more structured scan treats consecutive identical characters as windows. Maintain two pointers representing the current run of repeating characters. As you iterate through the string, extend the window while characters match and shrink/reset when they differ. Each update modifies only one index, so the string is scanned once to rebuild the longest run information. The key idea is tracking run lengths directly instead of evaluating all possible substrings. This keeps the logic linear and avoids redundant comparisons. Although each query still requires an O(n) pass, the implementation is clean and predictable, making it suitable when constraints are moderate.
For very large constraints, production-grade solutions typically rely on a segment tree that stores prefix, suffix, and maximum repeating lengths for each segment of the array. Updates then take O(log n). The simplified approaches here focus on clarity and correctness rather than advanced tree structures.
Recommended for interviews: Start with the naive recalculation approach to demonstrate understanding of the problem and how repeating segments are detected. Then discuss how repeated scans become expensive with many queries. Interviewers usually expect you to mention a segment tree or interval-based structure for O(log n) updates. Showing the progression from brute force scanning to a structured data structure demonstrates both problem-solving clarity and optimization awareness.
Approach 1: Naive Approach with Recalculation
def max_consecutive_chars(s):
max_len = 0
current_len = 1
for i in range(1, len(s)):
if s[i] == s[i - 1]:
current_len += 1
else:
max_len = max(max_len, current_len)
current_len = 1
return max(max_len, current_len)
def longest_substring_after_queries(s, query_characters, query_indices):
result = []
s = list(s)
for i in range(len(query_indices)):
s[query_indices[i]] = query_characters[i]
result.append(max_consecutive_chars(s))
return result
# Example usage
s = "babacc"
query_characters = "bcb"
query_indices = [1, 3, 3]
print(longest_substring_after_queries(s, query_characters, query_indices))import java.util.*;
public class LongestSubstring {
public static int maxRepeatedCharLength(String s) {
int maxLength = 0, currentLength = 1;
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == s.charAt(i - 1)) {
currentLength++;
} else {
maxLength = Math.max(maxLength, currentLength);
currentLength = 1;
}
}
return Math.max(maxLength, currentLength);
}
public static int[] longestSubstringAfterQueries(String s, String queryCharacters, int[] queryIndices) {
int[] result = new int[queryIndices.length];
StringBuilder sb = new StringBuilder(s);
for (int i = 0; i < queryIndices.length; i++) {
sb.setCharAt(queryIndices[i], queryCharacters.charAt(i));
result[i] = maxRepeatedCharLength(sb.toString());
}
return result;
}
public static void main(String[] args) {
String s = "babacc";
String queryCharacters = "bcb";
int[] queryIndices = {1, 3, 3};
int[] result = longestSubstringAfterQueries(s, queryCharacters, queryIndices);
System.out.println(Arrays.toString(result));
}
}#include <iostream>
#include <string>
#include <vector>
int getMaxSubstringLength(std::string &s) {
int maxLength = 0, currentLength = 1;
for (size_t i = 1; i < s.size(); ++i) {
if (s[i] == s[i - 1]) {
currentLength++;
} else {
maxLength = std::max(maxLength, currentLength);
currentLength = 1;
}
}
return std::max(maxLength, currentLength);
}
std::vector<int> longestSubstringAfterQueries(std::string s, std::string queryCharacters, std::vector<int> queryIndices) {
std::vector<int> result(queryIndices.size());
for (size_t i = 0; i < queryIndices.size(); ++i) {
s[queryIndices[i]] = queryCharacters[i];
result[i] = getMaxSubstringLength(s);
}
return result;
}
int main() {
std::string s = "babacc";
std::string queryCharacters = "bcb";
std::vector<int> queryIndices = {1, 3, 3};
std::vector<int> result = longestSubstringAfterQueries(s, queryCharacters, queryIndices);
for (int len : result) {
std::cout << len << " ";
}
return 0;
}function getMaxSubStringLength(s) {
let maxLen = 0, currentLen = 1;
for (let i = 1; i < s.length; i++) {
if (s[i] === s[i - 1]) {
currentLen++;
} else {
maxLen = Math.max(maxLen, currentLen);
currentLen = 1;
}
}
return Math.max(maxLen, currentLen);
}
function longestSubstringAfterQueries(s, queryCharacters, queryIndices) {
const results = [];
s = s.split("");
queryIndices.forEach((index, i) => {
s[index] = queryCharacters[i];
results.push(getMaxSubStringLength(s.join("")));
});
return results;
}
// Example usage
let s = "babacc";
let queryCharacters = "bcb";
let queryIndices = [1, 3, 3];
console.log(longestSubstringAfterQueries(s, queryCharacters, queryIndices));#include <stdio.h>
#include <string.h>
int maxConsecutiveChars(char *str, int len) {
int maxLen = 0, currentLen = 1;
for (int i = 1; i < len; i++) {
if (str[i] == str[i - 1]) {
currentLen++;
} else {
if (currentLen > maxLen) maxLen = currentLen;
currentLen = 1;
}
}
if (currentLen > maxLen) maxLen = currentLen;
return maxLen;
}
void longestSubstringAfterQueries(char *s, char *queryCharacters, int *queryIndices, int k, int *output) {
int length = strlen(s);
for (int i = 0; i < k; i++) {
s[queryIndices[i]] = queryCharacters[i];
output[i] = maxConsecutiveChars(s, length);
}
}
int main() {
char s[] = "babacc";
char queryCharacters[] = "bcb";
int queryIndices[] = {1, 3, 3};
int k = 3;
int output[k];
longestSubstringAfterQueries(s, queryCharacters, queryIndices, k, output);
for (int i = 0; i < k; i++) {
printf("%d ", output[i]);
}
return 0;
}using System;
class LongestSubstring {
static int MaxRepeatedCharLength(string s) {
int maxLength = 0, currentLength = 1;
for (int i = 1; i < s.Length; i++) {
if (s[i] == s[i - 1]) {
currentLength++;
} else {
maxLength = Math.Max(maxLength, currentLength);
currentLength = 1;
}
}
return Math.Max(maxLength, currentLength);
}
static int[] LongestSubstringAfterQueries(string s, string queryCharacters, int[] queryIndices) {
char[] chars = s.ToCharArray();
int[] result = new int[queryIndices.Length];
for (int i = 0; i < queryIndices.Length; i++) {
chars[queryIndices[i]] = queryCharacters[i];
result[i] = MaxRepeatedCharLength(new string(chars));
}
return result;
}
static void Main() {
string s = "babacc";
string queryCharacters = "bcb";
int[] queryIndices = {1, 3, 3};
int[] result = LongestSubstringAfterQueries(s, queryCharacters, queryIndices);
Console.WriteLine(string.Join(", ", result));
}
}In the Python implementation, we convert the string to a list for in-place character updates. After each query, we modify the string and use a utility function to determine the length of the longest contiguous characters.
Time Complexity: O(k * n), iterating over the string for each query.
Space Complexity: O(1) for additional data structures, beyond space for result storage.
Approach 2: Optimized Sliding Window Approach
def update_and_find_max(s, index, new_char, max_len):
s[index] = new_char
left = right = index
while left - 1 >= 0 and s[left - 1] == s[index]:
left -= 1
while right + 1 < len(s) and s[right + 1] == s[index]:
right += 1
current_len = right - left + 1
max_len[0] = max(max_len[0], current_len)
def longest_substring_after_queries(s, query_characters, query_indices):
s = list(s)
max_len = [1]
update_and_find_max(s, 0, s[0], max_len)
result = []
for idx, char in zip(query_indices, query_characters):
update_and_find_max(s, idx, char, max_len)
result.append(max_len[0])
return result
s = "babacc"
query_characters = "bcb"
query_indices = [1, 3, 3]
print(longest_substring_after_queries(s, query_characters, query_indices))import java.util.*;
public class LongestSubstring {
private static void updateAndFindMax(char[] s, int index, char newChar, int[] maxLen) {
int len = s.length;
int left = index, right = index;
s[index] = newChar;
while (left - 1 >= 0 && s[left - 1] == s[index]) left--;
while (right + 1 < len && s[right + 1] == s[index]) right++;
int currLen = right - left + 1;
maxLen[0] = Math.max(maxLen[0], currLen);
}
public static int[] longestSubstringAfterQueries(String s, String queryCharacters, int[] queryIndices) {
int[] maxLen = {1};
char[] charArray = s.toCharArray();
updateAndFindMax(charArray, 0, charArray[0], maxLen);
int[] result = new int[queryIndices.length];
for (int i = 0; i < queryIndices.length; i++) {
updateAndFindMax(charArray, queryIndices[i], queryCharacters.charAt(i), maxLen);
result[i] = maxLen[0];
}
return result;
}
public static void main(String[] args) {
String s = "babacc";
String queryCharacters = "bcb";
int[] queryIndices = {1, 3, 3};
int[] result = longestSubstringAfterQueries(s, queryCharacters, queryIndices);
System.out.println(Arrays.toString(result));
}
}#include <iostream>
#include <string>
#include <vector>
void updateAndFindMax(std::string &s, int index, char newChar, int &maxLen) {
int len = s.length();
int left = index, right = index;
s[index] = newChar;
while (left - 1 >= 0 && s[left - 1] == s[index]) left--;
while (right + 1 < len && s[right + 1] == s[index]) right++;
int currLen = right - left + 1;
maxLen = std::max(maxLen, currLen);
}
std::vector<int> longestSubstringAfterQueries(std::string s, std::string queryCharacters, std::vector<int> queryIndices) {
int initMaxLen = 1;
updateAndFindMax(s, 0, s[0], initMaxLen);
std::vector<int> result(queryIndices.size());
for (size_t i = 0; i < queryIndices.size(); i++) {
updateAndFindMax(s, queryIndices[i], queryCharacters[i], initMaxLen);
result[i] = initMaxLen;
}
return result;
}
int main() {
std::string s = "babacc";
std::string queryCharacters = "bcb";
std::vector<int> queryIndices = {1, 3, 3};
std::vector<int> result = longestSubstringAfterQueries(s, queryCharacters, queryIndices);
for (int length : result) {
std::cout << length << " ";
}
return 0;
}function updateAndFindMax(s, index, newChar, maxLen) {
s[index] = newChar;
let left = index, right = index;
while (left - 1 >= 0 && s[left - 1] === s[index]) left--;
while (right + 1 < s.length && s[right + 1] === s[index]) right++;
const currentLen = right - left + 1;
maxLen[0] = Math.max(maxLen[0], currentLen);
}
function longestSubstringAfterQueries(s, queryCharacters, queryIndices) {
const arr = s.split("");
const maxLen = [1];
updateAndFindMax(arr, 0, arr[0], maxLen);
const results = [];
queryIndices.forEach((q, i) => {
updateAndFindMax(arr, q, queryCharacters[i], maxLen);
results.push(maxLen[0]);
});
return results;
}
// Example usage
const s = "babacc";
const queryCharacters = "bcb";
const queryIndices = [1, 3, 3];
console.log(longestSubstringAfterQueries(s, queryCharacters, queryIndices));#include <stdio.h>
#include <string.h>
void updateAndFindMax(char *s, int index, char newChar, int *maxLen) {
int len = strlen(s);
int left = index, right = index;
s[index] = newChar;
while (left - 1 >= 0 && s[left - 1] == s[index]) left--;
while (right + 1 < len && s[right + 1] == s[index]) right++;
int currLen = right - left + 1;
if (currLen > *maxLen) *maxLen = currLen;
}
void longestSubstringAfterQueries(char *s, char *queryCharacters, int *queryIndices, int k, int *output) {
int initMaxLen = 1;
updateAndFindMax(s, 0, s[0], &initMaxLen);
for (int i = 0; i < k; i++) {
updateAndFindMax(s, queryIndices[i], queryCharacters[i], &initMaxLen);
output[i] = initMaxLen;
}
}
int main() {
char s[] = "babacc";
char queryCharacters[] = "bcb";
int queryIndices[] = {1, 3, 3};
int k = 3;
int output[k];
longestSubstringAfterQueries(s, queryCharacters, queryIndices, k, output);
for (int i = 0; i < k; i++) {
printf("%d ", output[i]);
}
return 0;
}using System;
class LongestSubstring {
static void UpdateAndFindMax(char[] s, int index, char newChar, ref int maxLen) {
s[index] = newChar;
int left = index, right = index;
while (left - 1 >= 0 && s[left - 1] == s[index]) left--;
while (right + 1 < s.Length && s[right + 1] == s[index]) right++;
int currentLen = right - left + 1;
maxLen = Math.Max(maxLen, currentLen);
}
static int[] LongestSubstringAfterQueries(string s, string queryCharacters, int[] queryIndices) {
char[] chars = s.ToCharArray();
int maxLen = 1;
UpdateAndFindMax(chars, 0, chars[0], ref maxLen);
int[] result = new int[queryIndices.Length];
for (int i = 0; i < queryIndices.Length; i++) {
UpdateAndFindMax(chars, queryIndices[i], queryCharacters[i], ref maxLen);
result[i] = maxLen;
}
return result;
}
static void Main() {
string s = "babacc";
string queryCharacters = "bcb";
int[] queryIndices = {1, 3, 3};
int[] result = LongestSubstringAfterQueries(s, queryCharacters, queryIndices);
Console.WriteLine(string.Join(", ", result));
}
}In Python, the list and tuple approach ensures mutable updates and controlled indices dictating where recalibrations on substring size need be implemented and observed, syncing memory savings and efficiency.
Time Complexity: O(k * m), m being fixed to targeted local regions per update.
Space Complexity: O(1) outside the output holding structure.
Approach 3: Segment Tree
The segment tree divides the entire interval into multiple non-continuous sub-intervals, and the number of sub-intervals does not exceed log(width). To update the value of an element, you only need to update log(width) intervals, and these intervals are all contained in a large interval that contains the element. When modifying the interval, you need to use lazy tags to ensure efficiency.
- Each node of the segment tree represents an interval;
- The segment tree has a unique root node, which represents the entire statistical range, such as
[1, n]; - Each leaf node of the segment tree represents an elementary interval of length
1,[x, x]; - For each internal node
[l, r], its left child is[l, mid], and the right child is[mid + 1, r], wheremid = \frac{l + r}{2};
For this problem, the information maintained by the segment tree node includes:
- The number of longest consecutive characters in the prefix,
lmx; - The number of longest consecutive characters in the suffix,
rmx; - The number of longest consecutive characters in the interval,
mx. - The left endpoint
land the right endpointrof the interval.
The time complexity is O(n times log n), and the space complexity is O(n times log n). Where n is the length of the string s.
class Node {
l: number;
r: number;
lmx: number;
rmx: number;
mx: number;
constructor(l: number, r: number) {
this.l = l;
this.r = r;
this.lmx = 1;
this.rmx = 1;
this.mx = 1;
}
}
class SegmentTree {
private s: string[];
private tr: Node[];
constructor(s: string) {
this.s = s.split('');
this.tr = Array(s.length * 4)
.fill(null)
.map(() => new Node(0, 0));
this.build(1, 1, s.length);
}
private build(u: number, l: number, r: number): void {
this.tr[u] = new Node(l, r);
if (l === r) {
return;
}
const mid = (l + r) >> 1;
this.build(u << 1, l, mid);
this.build((u << 1) | 1, mid + 1, r);
this.pushup(u);
}
public modify(u: number, x: number, v: string): void {
if (this.tr[u].l === x && this.tr[u].r === x) {
this.s[x - 1] = v;
return;
}
const mid = (this.tr[u].l + this.tr[u].r) >> 1;
if (x <= mid) {
this.modify(u << 1, x, v);
} else {
this.modify((u << 1) | 1, x, v);
}
this.pushup(u);
}
public query(u: number, l: number, r: number): number {
if (this.tr[u].l >= l && this.tr[u].r <= r) {
return this.tr[u].mx;
}
const mid = (this.tr[u].l + this.tr[u].r) >> 1;
let ans = 0;
if (r <= mid) {
ans = this.query(u << 1, l, r);
} else if (l > mid) {
ans = Math.max(ans, this.query((u << 1) | 1, l, r));
} else {
ans = Math.max(this.query(u << 1, l, r), this.query((u << 1) | 1, l, r));
}
return ans;
}
private pushup(u: number): void {
const root = this.tr[u];
const left = this.tr[u << 1];
const right = this.tr[(u << 1) | 1];
root.mx = Math.max(left.mx, right.mx);
root.lmx = left.lmx;
root.rmx = right.rmx;
const a = left.r - left.l + 1;
const b = right.r - right.l + 1;
if (this.s[left.r - 1] === this.s[right.l - 1]) {
if (left.lmx === a) {
root.lmx += right.lmx;
}
if (right.rmx === b) {
root.rmx += left.rmx;
}
root.mx = Math.max(root.mx, left.rmx + right.lmx);
}
}
}
function longestRepeating(s: string, queryCharacters: string, queryIndices: number[]): number[] {
const tree = new SegmentTree(s);
const k = queryIndices.length;
const ans: number[] = new Array(k);
const n = s.length;
for (let i = 0; i < k; ++i) {
const x = queryIndices[i] + 1;
const v = queryCharacters[i];
tree.modify(1, x, v);
ans[i] = tree.query(1, 1, n);
}
return ans;
}type Node struct {
l, r int
lmx, rmx, mx int
}
type SegmentTree struct {
s []byte
tr []*Node
}
func NewNode(l, r int) *Node {
return &Node{l: l, r: r, lmx: 1, rmx: 1, mx: 1}
}
func NewSegmentTree(s string) *SegmentTree {
n := len(s)
tree := &SegmentTree{s: []byte(s), tr: make([]*Node, n<<2)}
tree.build(1, 1, n)
return tree
}
func (tree *SegmentTree) build(u, l, r int) {
tree.tr[u] = NewNode(l, r)
if l == r {
return
}
mid := (l + r) >> 1
tree.build(u<<1, l, mid)
tree.build(u<<1|1, mid+1, r)
tree.pushup(u)
}
func (tree *SegmentTree) modify(u, x int, v byte) {
if tree.tr[u].l == x && tree.tr[u].r == x {
tree.s[x-1] = v
return
}
mid := (tree.tr[u].l + tree.tr[u].r) >> 1
if x <= mid {
tree.modify(u<<1, x, v)
} else {
tree.modify(u<<1|1, x, v)
}
tree.pushup(u)
}
func (tree *SegmentTree) query(u, l, r int) int {
if tree.tr[u].l >= l && tree.tr[u].r <= r {
return tree.tr[u].mx
}
mid := (tree.tr[u].l + tree.tr[u].r) >> 1
ans := 0
if r <= mid {
ans = tree.query(u<<1, l, r)
} else if l > mid {
ans = max(ans, tree.query(u<<1|1, l, r))
} else {
ans = max(tree.query(u<<1, l, r), tree.query(u<<1|1, l, r))
}
return ans
}
func (tree *SegmentTree) pushup(u int) {
root := tree.tr[u]
left := tree.tr[u<<1]
right := tree.tr[u<<1|1]
root.mx = max(left.mx, right.mx)
root.lmx = left.lmx
root.rmx = right.rmx
a := left.r - left.l + 1
b := right.r - right.l + 1
if tree.s[left.r-1] == tree.s[right.l-1] {
if left.lmx == a {
root.lmx += right.lmx
}
if right.rmx == b {
root.rmx += left.rmx
}
root.mx = max(root.mx, left.rmx+right.lmx)
}
}
func longestRepeating(s string, queryCharacters string, queryIndices []int) (ans []int) {
tree := NewSegmentTree(s)
n := len(s)
for i, v := range queryCharacters {
x := queryIndices[i] + 1
tree.modify(1, x, byte(v))
ans = append(ans, tree.query(1, 1, n))
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Naive Approach with Recalculation | Time Complexity: O(k * n), iterating over the string for each query. |
| Optimized Sliding Window Approach | Time Complexity: O(k * m), m being fixed to targeted local regions per update. |
| Segment Tree | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Recalculation | O(n) per query | O(1) | Good for understanding the problem or when the number of updates is small |
| Sliding Window Style Linear Scan | O(n) per query | O(1) | Cleaner linear pass that tracks consecutive runs without evaluating substrings |
| Segment Tree Optimization | O(log n) per update | O(n) | Best for large inputs with many updates where recomputation becomes too slow |
Frequently asked questions
Is Longest Substring of One Repeating Character easy or hard?
The problem is classified as Hard because it combines dynamic updates with substring queries. The naive solution is straightforward, but designing an efficient O(log n) update strategy using a segment tree requires strong understanding of range data structures.
Longest Substring of One Repeating Character Python/Java solution
Python and Java implementations typically either scan the string after each update or implement a segment tree to maintain segment information. The segment tree version provides O(log n) updates, while the simpler scan approach runs in O(n) per query.
How to solve Longest Substring of One Repeating Character in O(n)?
Process the string with a single linear scan that tracks consecutive runs of identical characters. Maintain a counter for the current run and update a maximum length variable whenever the run grows. After each update to the string, repeat the scan to compute the longest repeating substring in O(n) time.
What is the best approach for Longest Substring of One Repeating Character?
The most efficient solution uses a segment tree that stores the longest repeating substring length for each segment along with prefix and suffix run lengths. Each character update modifies a single leaf and recalculates parent nodes in O(log n) time. This allows the longest repeating substring to be retrieved after every query efficiently.
Is Longest Substring of One Repeating Character asked at Google/Amazon/Meta?
Problems involving dynamic string updates and longest repeating segments appear in interviews at companies like Google, Amazon, and Meta. They are commonly used to evaluate knowledge of segment trees, interval merging, and efficient update/query data structures.
What data structure is used in Longest Substring of One Repeating Character?
The optimal solution uses a segment tree. Each node stores the maximum repeating substring length inside the segment along with prefix and suffix run lengths, allowing fast recomputation when a character changes.
What is the time complexity of Longest Substring of One Repeating Character?
A simple recalculation approach scans the string after every update, giving O(n) time per query and O(n * q) overall for q updates. A segment tree optimization reduces update time to O(log n) while maintaining the longest repeating substring in each node.