994. Longest Run After Updates
A banner printer keeps a row of tiles, each stamped with one lowercase letter; the row is given as the string s. A maintenance log then replaces tiles one at a time: the i-th entry stamps the letter letters[i] onto the tile at 0-indexed position indices[i], overwriting whatever was there. The entries are applied in order, and the two arrays have the same length.
After every single replacement, the printer wants to know how long the longest block of consecutive tiles carrying the same letter is. Return an array result with one entry per log entry, where result[i] is that longest block length measured right after the i-th replacement. A replacement may stamp the letter that is already there. The string is never empty.
Example 1
- Input:
- s = "aabbbc", letters = ["b","a","c"], indices = [1,3,4]
- Output:
- [4,2,2]
- Explanation:
The row becomes abbbbc (longest run 4), then abbabc (longest run 2), then abbacc (longest run 2).
Example 2
- Input:
- s = "xyz", letters = ["y","y"], indices = [0,2]
- Output:
- [2,3]
- Explanation:
yyz has a run of 2; yyy has a run of 3.
Example 3
- Input:
- s = "qqqq", letters = ["r","q"], indices = [2,2]
- Output:
- [2,4]
- Explanation:
qqrq has longest run 2; restoring the q gives qqqq with run 4.
Constraints
- 1 ≤ s.length ≤ 105
- letters.length == indices.length, 1 ≤ letters.length ≤ 105
sandlettersconsist of lowercase English letters- 0 ≤ indices[i] < s.length
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 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O((n + q) log n)
- Space
- O(n)