Show problems as
Classic problem #2213HardArrayStringSegment TreeOrdered Set

Longest Substring of One Repeating Character

Real-world version: Repainted Strip Runs
Tracked in this browser only
Read Longest Substring of One Repeating Character on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard 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)

More on the same topics