Longest Substring of One Repeating Character
Asked at Microsoft
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.
Asked At
| 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.
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
class 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.