Skip to content

2213. Longest Substring of One Repeating Character

Difficulty Topics

Description

You are given a 0-indexed string s. You are also given a 0-indexed string queryCharacters of length k and a 0-indexed array of integer indices queryIndices of length k, both of which are used to describe k queries.

The ith query updates the character in s at index queryIndices[i] to the character queryCharacters[i].

Return an array lengths of length k where lengths[i] is the length of the longest substring of s consisting of only one repeating character after the ith query is performed.

 

Example 1:

Input: s = "babacc", queryCharacters = "bcb", queryIndices = [1,3,3]
Output: [3,3,4]
Explanation: 
- 1st query updates s = "bbbacc". The longest substring consisting of one repeating character is "bbb" with length 3.
- 2nd query updates s = "bbbccc". 
  The longest substring consisting of one repeating character can be "bbb" or "ccc" with length 3.
- 3rd query updates s = "bbbbcc". The longest substring consisting of one repeating character is "bbbb" with length 4.
Thus, we return [3,3,4].

Example 2:

Input: s = "abyzz", queryCharacters = "aa", queryIndices = [2,1]
Output: [2,3]
Explanation:
- 1st query updates s = "abazz". The longest substring consisting of one repeating character is "zz" with length 2.
- 2nd query updates s = "aaazz". The longest substring consisting of one repeating character is "aaa" with length 3.
Thus, we return [2,3].

 

Constraints:

  • 1 <= s.length <= 105
  • s consists of lowercase English letters.
  • k == queryCharacters.length == queryIndices.length
  • 1 <= k <= 105
  • queryCharacters consists of lowercase English letters.
  • 0 <= queryIndices[i] < s.length

Solution

longest-substring-of-one-repeating-character.py
from sortedcontainers import SortedList

class Solution:
    def longestRepeating(self, s: str, qc: str, qi: List[int]) -> List[int]:
        M = 10 ** 6
        n = len(s)
        k = len(qc)

        s = list(s)

        sl = SortedList()
        h = SortedList()

        curr = 0

        for x, group in groupby(s):
            length = sum(1 for c in group)
            sl.add((curr, curr + length - 1))
            h.add(length)
            curr += length

        def add(x, y):
            sl.add((x, y))
            h.add(y - x + 1)

        def remove(x, y):
            sl.remove((x, y))
            h.remove(y - x + 1)

        def split(i):
            index = sl.bisect_right((i, M)) - 1

            left, right = sl[index]
            remove(left, right)

            if left != i:
                add(left, i - 1)

            add(i, i)

            if right != i:
                add(i + 1, right)

        def merge(index):
            if index + 1 >= len(sl): return

            left1, right1 = sl[index]
            left2, right2 = sl[index + 1]

            if s[right1] != s[left2]: return

            remove(left1, right1)
            remove(left2, right2)
            add(left1, right2)

        res = []

        for i, c in zip(qi, qc):
            if s[i] == c:
                res.append(h[-1])
                continue

            split(i)

            index = sl.bisect_right((i, M)) - 1

            s[i] = c
            merge(index)

            if index - 1 >= 0:
                merge(index - 1)

            res.append(h[-1])

        return res