Leetcode 2213. Longest Substring of One Repeating Character

문제

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.

0부터 인덱싱되는 문자열 s가 주어집니다. 또한 길이가 k인 0부터 인덱싱되는 문자열 queryCharacters와 길이가 k인 0부터 인덱싱되는 정수 배열 queryIndices가 주어지며, 이 둘은 총 k개의 쿼리를 나타냅니다.

i번째 쿼리는 s의 queryIndices[i] 위치에 있는 문자를 queryCharacters[i]로 변경합니다.

길이가 k인 배열 lengths를 반환하세요.

여기서 lengths[i]는 i번째 쿼리를 수행한 직후, 문자열 s에서 하나의 동일한 문자만 연속해서 반복되는 부분 문자열 중 가장 긴 것의 길이입니다.

예를 들어 s = "aabbbcc"라면 동일한 문자가 연속되는 부분은 "aa", "bbb", "cc" 등이 있으므로 가장 긴 길이는 3입니다.

---

예시

입력:
s = "babacc", queryCharacters = "bcb", queryIndices = [1,3,3]

출력:
[3,3,4]

설명:

• 첫 번째 쿼리를 수행하면 s = "bbbacc"가 됩니다.
  하나의 문자가 반복되는 가장 긴 부분 문자열은 "bbb"이며, 길이는 3입니다.

• 두 번째 쿼리를 수행하면 s = "bbbccc"가 됩니다.
  하나의 문자가 반복되는 가장 긴 부분 문자열은 "bbb" 또는 "ccc"이며, 길이는 3입니다.

• 세 번째 쿼리를 수행하면 s = "bbbbcc"가 됩니다.
  하나의 문자가 반복되는 가장 긴 부분 문자열은 "bbbb"이며, 길이는 4입니다.

따라서 [3,3,4]를 반환합니다.

---

제한

• $1 \le s.length \le 105$
• $k == queryCharacters.length == queryIndices.length$
• $1 \le k \le 10^5$
• $0 \le queryIndices[i] < s.length$
• s 는 영어 소문자로만 이루어져 있다.
• queryCharacters 는 영어 소문자로만 이루어져 있다.

---

풀이

• 각 쿼리마다 문자열 전체를 다시 탐색하면 O(nk)가 되어 시간 초과가 발생할 수 있다.

• 한 글자만 변경되는 점 업데이트이므로 세그먼트 트리를 사용한다.

• 세그먼트 트리의 각 노드에는 해당 구간에 대해 다음 정보를 저장한다.

  • left_char: 구간의 가장 왼쪽 문자
  • right_char: 구간의 가장 오른쪽 문자
  • prefix: 왼쪽 끝에서부터 같은 문자가 연속되는 길이
  • suffix: 오른쪽 끝에서부터 같은 문자가 연속되는 길이
  • maximum: 구간 내부에서 같은 문자가 가장 길게 연속되는 길이
  • length: 구간 전체 길이

• 두 자식 노드 left, right를 합칠 때:

  • left.right_char != right.left_char라면 두 구간의 경계를 넘어 이어지는 연속 문자열이 없으므로

    • prefix = left.prefix
    • suffix = right.suffix
    • maximum = max(left.maximum, right.maximum)

  • left.right_char == right.left_char라면 경계의 동일한 문자가 이어질 수 있다.

    • 왼쪽 구간 전체가 하나의 문자로 이루어져 있다면
      prefix = left.length + right.prefix
    • 오른쪽 구간 전체가 하나의 문자로 이루어져 있다면
      suffix = left.suffix + right.length
    • 경계를 가로지르는 연속 길이는
      left.suffix + right.prefix
    • 따라서
      maximum = max(left.maximum, right.maximum, left.suffix + right.prefix)

• 각 쿼리에서는 queryIndices[i]에 해당하는 리프 노드의 문자를 변경한 뒤, 루트까지 올라가며 위 정보를 다시 계산한다.

• 쿼리가 끝난 후 루트 노드의 maximum이 현재 문자열 전체에서 동일한 문자가 가장 길게 연속되는 길이가 된다.

• 세그먼트 트리 생성은 O(n), 한 번의 업데이트는 O(log n)이므로 전체 시간 복잡도는 O(n + k log n), 공간 복잡도는 O(n)이다.

class SegData:
    def __init__(
        self,
        left_char: str = "",
        right_char: str = "",
        prefix: int = 0,
        suffix: int = 0,
        maximum: int = 0,
        length: int = 0,
    ):
        self.left_char = left_char
        self.right_char = right_char

        self.prefix = prefix
        self.suffix = suffix

        self.maximum = maximum
        self.length = length


class SegTree:
    def __init__(self, s: str):
        self.n = len(s)

        # 1st : repeating character, 2nd : repeating count ( maximum )
        self.tree: List[SegData] = [None] * (self.n * 4 + 1)

        self.build(0, self.n - 1, 1, s)

    def merge(self, left: SegData, right: SegData) -> SegData:
        if left.right_char != right.left_char:
            return SegData(
                left.left_char,
                right.right_char,
                left.prefix,
                right.suffix,
                max(left.maximum, right.maximum),
                left.length + right.length,
            )

        prefix = (
            left.length + right.prefix if left.maximum == left.length else left.prefix
        )
        suffix = (
            left.suffix + right.length
            if right.maximum == right.length
            else right.suffix
        )
        maximum = max(left.maximum, right.maximum, left.suffix + right.prefix)
        length = left.length + right.length

        return SegData(left.left_char, right.right_char, prefix, suffix, maximum, length)


    def build(
        self, seg_left: int, seg_right: int, tree_index: int, original: str
    ) -> None:
        if seg_left == seg_right:
            self.tree[tree_index] = SegData(
                original[seg_left], original[seg_right], 1, 1, 1, 1
            )
            return

        mid = (seg_left + seg_right) // 2
        self.build(seg_left, mid, tree_index * 2, original)
        self.build(mid + 1, seg_right, tree_index * 2 + 1, original)

        left = self.tree[tree_index * 2]
        right = self.tree[tree_index * 2 + 1]

        self.tree[tree_index] = self.merge(left, right)
        return 

    def _update(
        self, seg_left: int, seg_right: int, tree_index: int, index: int, value: str
    ):
        if seg_left > index or seg_right < index:
            return

        if seg_left == seg_right:
            self.tree[tree_index].left_char = value
            self.tree[tree_index].right_char = value
            return

        mid = (seg_left + seg_right) // 2
        if index <= mid:
            self._update(seg_left, mid, tree_index * 2, index, value)
        else:
            self._update(mid + 1, seg_right, tree_index * 2 + 1, index, value)

        left = self.tree[tree_index * 2]
        right = self.tree[tree_index * 2 + 1]

        self.tree[tree_index] = self.merge(left, right)
        return 

    def update(self, index: int, value: str):
        self._update(0, self.n - 1, 1, index, value)


class Solution:
    def longestRepeating(
        self, s: str, queryCharacters: str, queryIndices: List[int]
    ) -> List[int]:
        seg = SegTree(s)
        ans = []

        for query_char, query_index in zip(queryCharacters, queryIndices):
            seg.update(query_index, query_char)
            ans.append(seg.tree[1].maximum)

        return ans