2213. Longest Substring of One Repeating Character
Asked at Microsoft
Difficulty
Hard
Time
O(n + k log n)
Space
O(n)
Pattern
Array
Companies
1
Problem
You are given a string s of lowercase letters. You are also given two arrays of the same length k: queryCharacters and queryIndices. Together they describe k updates.
The i-th update changes the character at position queryIndices[i] in s to queryCharacters[i]. Updates are permanent: each one builds on the string left by the previous update.
After each update, look at the current string and find the longest substring where every character is the same (a run of one repeated letter). Return an array lengths of length k, where lengths[i] is that longest run length right after the i-th update. A single character counts as a run of length 1.
One update, then measure the longest run
Constraints
- ●
1 <= s.length <= 10^5 - ●
s consists of lowercase English letters - ●
k == queryCharacters.length == queryIndices.length - ●
1 <= k <= 10^5 - ●
queryCharacters consists of lowercase English letters - ●
0 <= queryIndices[i] < s.length
Examples
s = "babacc", queryCharacters = "bcb", queryIndices = [1,3,3][3,3,4]s = "abyzz", queryCharacters = "aa", queryIndices = [2,1][2,3]Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Microsoft | Hard | View all Microsoft questions → |
How to Think About It
Brute force: after each query, update the string and scan every substring to find the longest run of identical characters.
Track runs of identical characters using a sorted container: on each update, merge or split the affected run and update the max.
Segment tree: each node stores (maxRun, prefixRun, suffixRun) for its segment, merging children in O(1).
On each query, update the leaf at the changed index and re-merge up the tree; the root gives the global max run length.
Optimal: segment tree approach runs in O(n log n) preprocessing and O(log n) per query.
Optimal Approach
Use a segment tree where each node stores three values: the longest run of identical characters in the segment, the length of the run starting from the left edge, and the length of the run ending at the right edge. When merging two children, if the rightmost character of the left child matches the leftmost character of the right child, the combined prefix extends into the right child and the combined suffix extends into the left child, and the crossing run (left.suffix + right.prefix) becomes a candidate for the new max. On each query, update the leaf and propagate the merge up the tree. The root node holds the answer for the entire string.
Segment tree keeps (max, prefix, suffix)
What Trips People Up in Real Interviews
Clarify that the string is modified in place across queries (cumulative changes), not reset between queries.
The segment tree merge is the trickiest part: track three values per node (max, prefix, suffix of consecutive identical chars).
For merge: new max = max(left.max, right.max, left.suffix + right.prefix) only when the boundary characters match.
Alternative with Ordered Set: maintain intervals of identical characters, binary search for the affected interval, and split/merge on update.
Edge case: single character string always returns 1. Ensure the segment tree handles size-1 correctly.
Solution Code
O(n + k log n) timeclass Solution:
def longestRepeating(self, s: str, queryCharacters: str, queryIndices: list) -> list:
n = len(s)
s = list(s)
def make_node(ch, is_one):
return [1 if is_one else 0, 1 if is_one else 0, 1 if is_one else 0, ch]
def merge(left, right):
if left[3] == '#':
return right
if right[3] == '#':
return left
mx = max(left[0], right[0])
pre = left[1]
if left[1] == (left[2] if left[3] != '#' else 0) and left[3] == right[3]:
pre = left[1] + right[1]
suf = right[2]
if right[2] == (right[1] if right[3] != '#' else 0) and left[3] == right[3]:
suf = left[2] + right[2]
if left[3] == right[3]:
mx = max(mx, left[2] + right[1])
return [mx, pre, suf, left[3]]
tree = [None] * (4 * n)
def build(node, l, r):
if l == r:
tree[node] = make_node(s[l], s[l] == '1')
return
mid = (l + r) // 2
build(2 * node, l, mid)
build(2 * node + 1, mid + 1, r)
tree[node] = merge(tree[2 * node], tree[2 * node + 1])
def update(node, l, r, idx):
if l == r:
tree[node] = make_node(s[l], s[l] == '1')
return
mid = (l + r) // 2
if idx <= mid:
update(2 * node, l, mid, idx)
else:
update(2 * node + 1, mid + 1, r, idx)
tree[node] = merge(tree[2 * node], tree[2 * node + 1])
build(1, 0, n - 1)
result = []
for i in range(len(queryIndices)):
s[queryIndices[i]] = queryCharacters[i]
update(1, 0, n - 1, queryIndices[i])
result.append(tree[1][0])
return resultFrequently Asked Questions
What is the Longest Substring of One Repeating Character problem?
You are given a lowercase string s and an integer array queries where queries[i] = [index, char]. For each query, replace s[index] with char, then find the length of the longest substring containing only one repeating character. Return an array of answers for each query.
How do you solve Longest Substring of One Repeating Character?
The optimal approach runs in O(n + k log n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Longest Substring of One Repeating Character?
Longest Substring of One Repeating Character is asked at Microsoft. It is a hard difficulty problem.
What are common mistakes on Longest Substring of One Repeating Character?
- Clarify that the string is modified in place across queries (cumulative changes), not reset between queries.
- The segment tree merge is the trickiest part: track three values per node (max, prefix, suffix of consecutive identical chars).
- For merge: new max = max(left.max, right.max, left.suffix + right.prefix) only when the boundary characters match.
- Alternative with Ordered Set: maintain intervals of identical characters, binary search for the affected interval, and split/merge on update.
- Edge case: single character string always returns 1. Ensure the segment tree handles size-1 correctly.