#2213

Hard

LeetCode Problem Workspace

Longest Substring of One Repeating Character

Solve Longest Substring of One Repeating Character by maintaining mergeable run information under character updates after each query.

array string segment tree ordered set

Problem Statement

You start with a lowercase string and then apply k point updates. Each update replaces one position with a new character, and after that change you must report the length of the longest contiguous substring made of one repeating character anywhere in the current string.

The difficulty is not finding one answer on a fixed string, but keeping that answer correct after many edits. In the example s = babacc with updates at indices [1,3,3] using characters bcb, the string becomes bbbacc, then bbbccc, then bbbbcc, so the outputs are [3,3,4] because the best repeated run changes when adjacent blocks merge across the updated index.

Examples

Example 1

Input: s = "babacc", queryCharacters = "bcb", queryIndices = [1,3,3]

Output: [3,3,4]

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]

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 <= 105
s consists of lowercase English letters.
k == queryCharacters.length == queryIndices.length
1 <= k <= 105
queryCharacters consists of lowercase English letters.
0 <= queryIndices[i] < s.length

Solution Approach

Why direct rescanning fails

After each update, a full left-to-right scan can recompute the longest repeated run in O(n), but that becomes O(nk) in the worst case. With n and k both up to 100000, this approach times out because one changed character may only affect local runs, yet rescanning throws away all previous structure.

Store mergeable run data in a segment tree

Build a segment tree over the string. For every node, store the leftmost character, rightmost character, the longest uniform prefix length, the longest uniform suffix length, the total segment length, and the best repeating run inside that segment. This information is enough to merge two children: the parent best is the maximum of left best, right best, and a cross-boundary run when the left rightmost character matches the right leftmost character.

Process each update with one point change and upward merges

For query i, update the leaf at queryIndices[i] to queryCharacters[i], then recompute all ancestors on the path to the root. Each recomputation uses the same merge rule, especially the case where the suffix of the left child and prefix of the right child combine into a longer block. After the update finishes, the root best value is the answer for that query.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Building the segment tree takes O(n). Each query performs one point update and O(log n) merges, so total time is O((n + k) log n) if you include build cost, or O(n + k log n) in the standard form. The tree stores constant metadata per node, so space is O(n).

What Interviewers Usually Probe

They mention fast point updates and repeated answers after each edit, which strongly hints that rescanning is the trap.
They ask how to combine two segments, which means they want the exact merge state instead of a vague tree description.
They focus on boundary behavior, especially when one updated character joins two equal runs across the middle.

Common Pitfalls or Variants

Common pitfalls

Storing only the best run per segment is not enough; you also need prefix and suffix run lengths plus boundary characters to merge correctly.
Forgetting the cross-boundary merge causes wrong answers when an update connects two same-character blocks into a longer run.
Treating this like a frequency problem is incorrect because the answer depends on contiguous runs, not total character counts.

Follow-up variants

Return the longest repeating run only after all updates, where a simple final scan would work but misses the online requirement of this problem.
Support range assignment updates instead of single-index updates, which usually needs lazy propagation on top of the same run metadata.
Track a different segment metric such as longest alternating substring, where the merge state changes because equality is no longer the winning condition.

FAQ

What is the main pattern in Longest Substring of One Repeating Character?

The core pattern is a segment tree over an array-like string, where each node stores enough boundary run information to merge two segments after a point update.

Why is a segment tree better than rescanning the string each time?

A full scan costs O(n) per query, which is too slow for 100000 updates. The segment tree limits each change to O(log n) recomputation because only one leaf-to-root path changes.

What data should each node store?

Store segment length, left boundary character, right boundary character, longest uniform prefix, longest uniform suffix, and the best repeating run inside the segment. Those fields fully determine the parent during merge.

Can this problem be solved with an ordered set instead?

Yes, there are ordered-set based ideas that track character runs and split or merge intervals after updates, but the implementation is usually trickier. In interviews, the segment tree is more direct because the merge rule matches the answer you need.

What is the most common bug in LeetCode 2213 implementations?

The most common bug is merging only the child answers and ignoring the new run formed by the left suffix plus right prefix when the boundary characters match.

terminal

Solution

Solution 1: 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(\textit{width})$. To update the value of an element, you only need to update $\log(\textit{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.

def max(a: int, b: int) -> int:
    return a if a > b else b


class Node:
    __slots__ = "l", "r", "lmx", "rmx", "mx"

    def __init__(self, l: int, r: int):
        self.l = l
        self.r = r
        self.lmx = self.rmx = self.mx = 1


class SegmentTree:
    __slots__ = "s", "tr"

    def __init__(self, s: str):
        self.s = list(s)
        n = len(s)
        self.tr: List[Node | None] = [None] * (n * 4)
        self.build(1, 1, n)

    def build(self, u: int, l: int, r: int):
        self.tr[u] = Node(l, r)
        if l == r:
            return
        mid = (l + r) // 2
        self.build(u << 1, l, mid)
        self.build(u << 1 | 1, mid + 1, r)
        self.pushup(u)

    def query(self, u: int, l: int, r: int) -> int:
        if self.tr[u].l >= l and self.tr[u].r <= r:
            return self.tr[u].mx
        mid = (self.tr[u].l + self.tr[u].r) // 2
        ans = 0
        if r <= mid:
            ans = self.query(u << 1, l, r)
        if l > mid:
            ans = max(ans, self.query(u << 1 | 1, l, r))
        return ans

    def modify(self, u: int, x: int, v: str):
        if self.tr[u].l == self.tr[u].r:
            self.s[x - 1] = v
            return
        mid = (self.tr[u].l + self.tr[u].r) // 2
        if x <= mid:
            self.modify(u << 1, x, v)
        else:
            self.modify(u << 1 | 1, x, v)
        self.pushup(u)

    def pushup(self, u: int):
        root, left, right = self.tr[u], self.tr[u << 1], self.tr[u << 1 | 1]
        root.lmx = left.lmx
        root.rmx = right.rmx
        root.mx = max(left.mx, right.mx)
        a, b = left.r - left.l + 1, right.r - right.l + 1
        if self.s[left.r - 1] == self.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)


class Solution:
    def longestRepeating(
        self, s: str, queryCharacters: str, queryIndices: List[int]
    ) -> List[int]:
        tree = SegmentTree(s)
        ans = []
        for x, v in zip(queryIndices, queryCharacters):
            tree.modify(1, x + 1, v)
            ans.append(tree.query(1, 1, len(s)))
        return ans

Continue Practicing

#2179 count good triplets in an array #2353 design a food rating system #2426 number of pairs satisfying inequality