0345HardArrayStringSegment TreeOrdered Set

Repainted Strip Runs

Tracked in this browser only

Trains the technique from

LeetCode 2213Longest Substring of One Repeating Character

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A lighting strip has one cell per character of s, and s[i] is the colour code currently shown by cell i.

A crew then works through k repaint orders. Order t sets cell queryIndices[t] to the colour queryCharacters[t], and the orders are applied one after another, so each order acts on the strip left behind by the previous one. A repaint may set a cell to the colour it already shows.

After each order, the crew records the length of the longest block of consecutive cells that all show the same colour. Return the list of those k recorded lengths, in order.

Examples

Example 1

Input: s = "wwxyyy", queryCharacters = "www", queryIndices = [2,5,3]
Output: [3,3,4]

The strip becomes `wwwyyy`, whose longest block is the run of three; then `wwwyyw`, still three; then `wwwwyw`, where the four leading cells share a colour.

Example 2

Input: s = "kkk", queryCharacters = "mk", queryIndices = [1,1]
Output: [1,3]

The first order turns the strip into `kmk`, whose longest same-colour block holds a single cell. The second order restores `kkk`, so the whole strip is one block of three.

Example 3

Input: s = "z", queryCharacters = "z", queryIndices = [0]
Output: [1]

The single cell is repainted to the colour it already shows, and the strip still holds one block of length 1.

Constraints

1 <= s.length <= 10^5
Every character of s is a lowercase English letter.
k == queryCharacters.length == queryIndices.length
1 <= k <= 10^5
Every character of queryCharacters is a lowercase English letter.
0 <= queryIndices[t] < s.length

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def longest_repeating(s: str, queryCharacters: str, queryIndices: list[int]) -> list[int]:

Java

public int[] longestRepeating(String s, String queryCharacters, int[] queryIndices)

The intended approach

Time O((n + k) log n)Space O(n) for the tree, plus O(k) for the returned answers

Hold the strip in a segment tree whose nodes carry the colours at their two edges, the length of the block touching the left edge, the length of the block touching the right edge, the best block strictly inside, and the node width. Two children combine in constant time: the only extra candidate block is the one that spans their shared boundary, which is real only when the colours meeting there agree. A repaint rewrites one leaf and recombines the nodes on its path to the root, and the root's best value is the answer for that order.

Pythonentry point: longest_repeating

def longest_repeating(s, queryCharacters, queryIndices):
    # Segment tree.  Each node keeps: leftmost colour, rightmost colour, the run
    # that starts at its left edge, the run that ends at its right edge, its best
    # inner run, and its width.  Merging two nodes only needs to test whether the
    # right edge of the left child matches the left edge of the right child.
    # Time O((n + k) log n).  Space O(n) for the tree plus O(k) for the answers.
    n = len(s)
    size = 1
    while size < n:
        size *= 2
    empty = (None, None, 0, 0, 0, 0)
    tree = [empty] * (2 * size)

    def merge(a, b):
        if a[5] == 0:
            return b
        if b[5] == 0:
            return a
        alc, arc, apre, asuf, abest, alen = a
        blc, brc, bpre, bsuf, bbest, blen = b
        joined = arc == blc
        pre = apre + (bpre if (apre == alen and joined) else 0)
        suf = bsuf + (asuf if (bsuf == blen and joined) else 0)
        best = abest if abest > bbest else bbest
        if joined and asuf + bpre > best:
            best = asuf + bpre
        return (alc, brc, pre, suf, best, alen + blen)

    for i in range(n):
        c = s[i]
        tree[size + i] = (c, c, 1, 1, 1, 1)
    for i in range(size - 1, 0, -1):
        tree[i] = merge(tree[2 * i], tree[2 * i + 1])

    out = []
    for step in range(len(queryIndices)):
        pos = queryIndices[step]
        c = queryCharacters[step]
        node = size + pos
        tree[node] = (c, c, 1, 1, 1, 1)
        node //= 2
        while node >= 1:
            tree[node] = merge(tree[2 * node], tree[2 * node + 1])
            node //= 2
        out.append(tree[1][4])
    return out

The obvious version

Keep the strip as a list of colours, apply each order, and after every order walk the whole strip once counting the current run to find the longest block.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_longest_run_after_each(s, queryCharacters, queryIndices):
    cells = list(s)
    out = []
    for step in range(len(queryIndices)):
        cells[queryIndices[step]] = queryCharacters[step]
        best = 1
        run = 1
        for i in range(1, len(cells)):
            if cells[i] == cells[i - 1]:
                run += 1
            else:
                run = 1
            if run > best:
                best = run
        out.append(best)
    return out

How this problem was checked

Reference solution executed against 9 test cases — 9 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in