Hard

Longest Substring of One Repeating Character

LAB

Given a lowercase string s, a string queryCharacters, and an equally sized array queryIndices, apply each replacement in order. Query i permanently sets s[queryIndices[i]] to queryCharacters[i]. After every update, report the length of the longest contiguous substring made from one repeated character. Return all reported lengths in query order.

EXAMPLES

Example 1

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

Output
[
  3,
  3,
  4
]

FUNCTION SHAPE

s: stringqueryCharacters: stringqueryIndices: intArray→intArray

SOLUTION NOTE

The five content fields in a recursive node are sufficient because its [lo, hi] bounds already reveal segment length. In a standalone immutable summary, storing length explicitly makes the combine contract self-contained.

Reveal reference solution +

pythonREFERENCE

from dataclasses import dataclass
from typing import List

@dataclass
class Info:
    length: int
    left_char: str
    right_char: str
    prefix: int
    suffix: int
    best: int

def merge(left: Info, right: Info) -> Info:
    same = left.right_char == right.left_char

    prefix = left.prefix
    if left.prefix == left.length and same:
        prefix += right.prefix

    suffix = right.suffix
    if right.suffix == right.length and same:
        suffix += left.suffix

    crossing = left.suffix + right.prefix if same else 0
    return Info(
        left.length + right.length,
        left.left_char, right.right_char,
        prefix, suffix,
        max(left.best, right.best, crossing),
    )

class SegmentTree:
    def __init__(self, s: str):
        self.n = len(s)
        self.tree = [None] * (4 * self.n)
        self._build(1, 0, self.n - 1, s)

    @staticmethod
    def _leaf(char: str) -> Info:
        return Info(1, char, char, 1, 1, 1)

    def _build(self, node: int, lo: int, hi: int, s: str) -> None:
        if lo == hi:
            self.tree[node] = self._leaf(s[lo])
            return
        mid = (lo + hi) // 2
        self._build(node * 2, lo, mid, s)
        self._build(node * 2 + 1, mid + 1, hi, s)
        self.tree[node] = merge(self.tree[node * 2], self.tree[node * 2 + 1])

    def update(self, index: int, char: str) -> None:
        self._update(1, 0, self.n - 1, index, char)

    def _update(
        self, node: int, lo: int, hi: int, index: int, char: str
    ) -> None:
        if lo == hi:
            self.tree[node] = self._leaf(char)
            return
        mid = (lo + hi) // 2
        if index <= mid:
            self._update(node * 2, lo, mid, index, char)
        else:
            self._update(node * 2 + 1, mid + 1, hi, index, char)
        self.tree[node] = merge(self.tree[node * 2], self.tree[node * 2 + 1])

    @property
    def answer(self) -> int:
        return self.tree[1].best

class Solution:
    def longestRepeating(
        self, s: str, queryCharacters: str, queryIndices: List[int]
    ) -> List[int]:
        tree = SegmentTree(s)
        answers = []
        for index, char in zip(queryIndices, queryCharacters):
            tree.update(index, char)
            answers.append(tree.answer)
        return answers

def solve(s, queryCharacters, queryIndices):
    return Solution().longestRepeating(s, queryCharacters, queryIndices)

TimeO(n + q log n)

SpaceO(n)

Open on LeetCode ↗