2213. Longest Substring of One Repeating Character

  • String
  • Segment Tree
  • Divide and Conquer
  • Array
TIME
O((n + k) log n)
SPACE
O(n)
problem on leetcode ↗source on github ↗

Intuition

Recomputing the longest single-character run after each update would be O(n) per query, O(n * k) overall, far too slow. But the answer is a mergeable property: if you know, for two adjacent blocks, their longest internal run plus the runs touching their edges, you can combine them in O(1). That's exactly a segment tree over the string.

The one subtlety is that a run can span the boundary between two children, so each node must remember its edge runs, not just its best.

Approach

Each segment tree node stores:

  • len the segment length
  • lc, rc the characters at its left and right edges
  • pre length of the longest run starting at the left edge
  • suf length of the longest run ending at the right edge
  • best length of the longest run anywhere inside

Merge (left, right):

best = max(left.best, right.best)
if left.rc == right.lc:
    best = max(best, left.suf + right.pre)        # run crossing the boundary

pre = left.pre + (right.pre if left.pc spans all of left and left.rc == right.lc else 0)
suf = right.suf + (left.suf if right.suf spans all of right and left.rc == right.lc else 0)

The pre/suf extensions only apply when a child is entirely one character, in which case the run continues into the sibling.

Per query: set the leaf's character, walk up re-merging along the path, then read best at the root.

An iterative array-based tree (size padded to a power of two) avoids recursion overhead; empty padding leaves are handled by treating a zero-length child as identity in the merge.

Complexity

  • Time: O((n + k) log n), O(n) build, O(log n) per update
  • Space: O(n), the node arrays

Edge Cases

  • Update that doesn't change the character → still correct (merge is idempotent)
  • Entire string one character → pre = suf = best = n
  • Single-character string → every query answers 1
  • Runs crossing node boundaries are the reason pre/suf are tracked at all
  • Padding leaves beyond n must not contribute; guard with len == 0

Code

from typing import List


class Solution:
    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:
        """
        2213. Longest Substring of One Repeating Character
        Time: O((n + k) log n)
        Space: O(n)
        """
        n = len(s)
        size = 1
        while size < n:
            size <<= 1

        # Per-node: prefix run, suffix run, best run, edge chars, segment length.
        pre = [0] * (2 * size)
        suf = [0] * (2 * size)
        best = [0] * (2 * size)
        lc = [0] * (2 * size)
        rc = [0] * (2 * size)
        ln = [0] * (2 * size)

        def pull(i: int) -> None:
            l, r = 2 * i, 2 * i + 1
            if ln[l] == 0:  # padding child acts as identity
                pre[i], suf[i], best[i] = pre[r], suf[r], best[r]
                lc[i], rc[i], ln[i] = lc[r], rc[r], ln[r]
                return
            if ln[r] == 0:
                pre[i], suf[i], best[i] = pre[l], suf[l], best[l]
                lc[i], rc[i], ln[i] = lc[l], rc[l], ln[l]
                return
            ln[i] = ln[l] + ln[r]
            lc[i], rc[i] = lc[l], rc[r]
            join = rc[l] == lc[r]
            b = best[l] if best[l] > best[r] else best[r]
            if join and suf[l] + pre[r] > b:
                b = suf[l] + pre[r]  # run crossing the boundary
            best[i] = b
            # a child that is entirely one character lets the run continue
            pre[i] = pre[l] + (pre[r] if (join and pre[l] == ln[l]) else 0)
            suf[i] = suf[r] + (suf[l] if (join and suf[r] == ln[r]) else 0)

        for i, ch in enumerate(s):
            j = size + i
            pre[j] = suf[j] = best[j] = ln[j] = 1
            lc[j] = rc[j] = ord(ch)
        for i in range(size - 1, 0, -1):
            pull(i)

        result = []
        for ch, idx in zip(queryCharacters, queryIndices):
            j = size + idx
            lc[j] = rc[j] = ord(ch)
            j >>= 1
            while j:
                pull(j)
                j >>= 1
            result.append(best[1])
        return result