Editorial for Sub Sub Strings

Use this editorial only when stuck, and do not copy-paste code from it.

Please be respectful to the problem author and editorialist. Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

Build a segment tree over the string. Each node stores:

the leftmost and rightmost characters in its range
the longest same-character prefix and suffix lengths
whether the whole range is a single character
the longest same-character run anywhere in the range

When merging two nodes, the answer is the maximum of:

the left child's best run
the right child's best run
the run formed across the boundary, if the left child's rightmost character equals the right child's leftmost character

Each query then returns the best run in $[a, b]$ in $O(\log n)$ time. Building the tree costs $O(n)$ , so the total time complexity is $O(n + q \log n)$ .

Solution (Python)

Code 1

from __future__ import annotations

from dataclasses import dataclass
from typing import Callable, Generic, List, TypeVar
import copy

T = TypeVar("T")


class SegmentTree(Generic[T]):
    def __init__(self, arr: List[T], combine: Callable[[T, T], T]) -> None:
        self.combine = combine
        self.length = len(arr)
        self.array = [0] * (self.length * 4 + 1)
        self.__build(1, 0, self.length - 1, arr)

    def __build(self, v: int, tl: int, tr: int, arr: List[T]) -> None:
        if tl == tr:
            self.array[v] = arr[tl]
        else:
            tm = (tl + tr) // 2
            self.__build(2 * v, tl, tm, arr)
            self.__build(2 * v + 1, tm + 1, tr, arr)
            self.array[v] = self.combine(self.array[2 * v], self.array[2 * v + 1])

    def update(self, index: int, value: T) -> None:
        self.__update(index, 1, 0, self.length - 1, value)

    def __update(self, index: int, v: int, tl: int, tr: int, value: T) -> None:
        if tl == tr:
            self.array[v] = value
            return

        tm = (tl + tr) // 2
        if index <= tm:
            self.__update(index, 2 * v, tl, tm, value)
        else:
            self.__update(index, 2 * v + 1, tm + 1, tr, value)

        self.array[v] = self.combine(self.array[2 * v], self.array[2 * v + 1])

    def query(self, l: int, r: int) -> T:
        return copy.copy(self.__query(1, 0, self.length - 1, l, r))

    def __query(self, v: int, tl: int, tr: int, l: int, r: int) -> T:
        if tl == l and tr == r:
            return self.array[v]

        tm = (tl + tr) // 2
        if r <= tm:
            return self.__query(2 * v, tl, tm, l, r)
        if l > tm:
            return self.__query(2 * v + 1, tm + 1, tr, l, r)
        return self.combine(
            self.__query(2 * v, tl, tm, l, tm),
            self.__query(2 * v + 1, tm + 1, tr, tm + 1, r),
        )


@dataclass
class Node:
    left_char: str
    right_char: str
    left_max: int
    right_max: int
    max: int
    one_char: bool


def combine(left: Node, right: Node) -> Node:
    res = Node("c", "c", 1, 1, 1, True)

    res.left_char = left.left_char
    res.right_char = right.right_char
    res.one_char = left.right_char == right.left_char and left.one_char and right.one_char

    if left.one_char and left.right_char == right.left_char:
        res.left_max = left.max + right.left_max
    else:
        res.left_max = left.left_max

    if right.one_char and left.right_char == right.left_char:
        res.right_max = right.max + left.right_max
    else:
        res.right_max = right.right_max

    res.max = max(left.max, right.max)
    if left.right_char == right.left_char:
        res.max = max(res.max, left.right_max + right.left_max)

    return res


n, q = (int(x) for x in input().split())
arr = [Node(x, x, 1, 1, 1, True) for x in input()]
tree = SegmentTree[Node](arr, combine)

for _ in range(q):
    a, b = (int(x) - 1 for x in input().split())
    print(tree.query(a, b).max)

Comments0

No comments yet

Be the first to comment.

Editorial for Sub Sub Strings

Approach

Solution (Python)

Comments0

New comment