999. Longest Run After Updates
A banner of n lamps shows the colour letters of s. A technician repaints lamps one at a time: repaint k sets lamp indices[k] % n (0-based) to colour letters[k]. If the two lists differ in length, only the first min(length) repaints are carried out.
After every repaint, record the length of the longest block of consecutive lamps with the same colour. Return all recorded lengths, in order, as an array (empty when there are no repaints).
Target time O((n + m) log n) and space O(n), where m is the number of repaints. Rescanning the whole banner after each repaint is too slow.
Example 1
- Input:
- s = "rrgbbbgrr"letters = ["g","b","g"]indices = [3,7,4]
- Output:
- [2,2,3]
- Explanation:
Repainting lamp 3 gives rrggbbgrr (longest block 2); lamp 7 gives rrggbbgbr (2); lamp 4 gives rrgggbgbr, where the three g's form a block of 3.
Example 2
- Input:
- s = "xxxyzzzzy"letters = ["z","z","y"]indices = [3,2,6]
- Output:
- [5,6,4]
- Explanation:
Lamp 3 becomes z: xxxzzzzzy has a block of 5; lamp 2 becomes z: xxzzzzzzy gives 6; lamp 6 becomes y: xxzzzzyzy leaves 4.
Constraints
1 ≤ s.length ≤ 105
s and letters contain lowercase letters only
0 ≤ letters.length, indices.length ≤ 2000
0 ≤ indices[k] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n + m log n)
- Space
- O(n)