Longest Valid Parentheses

Q: Существует ли решение задачи «Самая длинная правильная скобочная последовательность» с помощью динамического программирования?

Да. Пусть end[i] — длина самой длинной корректной подстроки, заканчивающейся на индексе i ; она равна 0, когда s[i] — это ( . Если s[i-1] — это ( , то end[i] = end[i-2] + 2 . Если это ) , рассмотрим j = i - end[i-1] - 1 — символ перед последовательностью, заканчивающейся на i-1 : когда s[j] — это ( , он обрамляет эту последовательность, и end[i] = end[i-1] + 2 + end[j-1] , где последнее слагаемое добавляет последовательность, примыкающую к ней слева. Ответ — наибольшее значение end[i] ; время работы и объём памяти составляют O(n) .

СложноСтек Динамическое программирование

+10

Дана строка s, состоящая только из символов ( и ). Найдите самую длинную подстроку (непрерывную последовательность символов), которая является правильной скобочной последовательностью: каждая ( в ней закрывается более поздней ), и скобки правильно вложены, как в (()()). Верните длину этой подстроки или 0, если в строке нет даже ().

Функция

longestValidParentheses(s: string) → integer

sstring: строка из символов ( и )
Возвращаетinteger: длина самой длинной корректно сформированной подстроки или 0, если такой нет

Ограничения

1 ≤ s.length ≤ 6 × 10⁴
Каждый символ s — это ( или ).

Примеры

Ввод: s = "()(())"
Вывод: 6
Пояснение: Вся строка составлена правильно: (), за которыми следует (()). Два правильно составленных фрагмента рядом образуют один правильно составленный фрагмент, поэтому ответ — все 6 символов.

Ввод: s = "())((())"
Вывод: 4
Пояснение: У ) с индексом 2 нет пары, поэтому ни один ответ не может пересекать его, а ( с индексом 3 никогда не закрывается. Самый длинный фрагмент — (()) с индекса 4 по 7, длиной 4, что длиннее () в начале.

Ввод: s = "))(("
Вывод: 0
Пояснение: Обе ) идут перед обеими (, поэтому ни одна ( не закрывается. Ни одна подстрока не является правильно сформированной, и ответ равен 0.

Дополнительный вопрос

Можешь также сообщить, где начинается самая длинная корректно сформированная подстрока, выбирая самую левую, если несколько подстрок имеют одинаковую длину?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Две вещи усложняют эту задачу по сравнению с проверкой одной строки. Корректно сформированные фрагменты объединяются, когда соприкасаются, поэтому () и (()), стоящие рядом, считаются одним фрагментом длиной 6. А один лишний символ, например ) в ())(()), разрывает строку, и ни один ответ не может пересечь этот разрыв. Проверка каждой начальной позиции требует O(n²). Решение — запоминать, где начался текущий фрагмент: для этого достаточно стека индексов с базовым маркером внизу, что позволяет выполнить алгоритм за один проход; а два прохода с обычными счётчиками обходятся вообще без стека.

Постройте подстроку от каждой начальной позиции

Верно, но не успевает на самых больших тестах

Идея

Просматривай подстроку слева направо, ведя баланс: увеличивай его на 1 для ( и уменьшай на 1 для ). Подстрока корректна тогда и только тогда, когда баланс никогда не опускается ниже 0 и в конце равен 0. Значение ниже 0 означает, что встретилась ), которой нечего закрывать.

Итак, зафиксируй начало и двигайся вправо, обновляя баланс по одному символу за раз. Каждый раз, когда он снова становится равным 0, участок от начала до текущего места корректен, и ты записываешь его длину. Как только баланс опустится ниже 0, остановись: эта ) останется несопоставленной в любом более длинном участке с этим началом. У каждой корректной подстроки есть некоторое начало, и ты перебираешь для неё каждый конец, поэтому ничего не будет пропущено.

Проблема — в затратах. В строке из 59998 символов (, за которыми следует (), баланс никогда не опускается ниже 0, поэтому при каждом начале проход продолжается до конца: около n²/2 = 1.8 × 10^9 шагов для n = 6 × 10^4. Большие тесты устроены именно так. (Проверять каждую подстроку с нуля, вместо того чтобы наращивать её, было бы ещё хуже: O(n³).)

Алгоритм

Установите best в 0.
Для каждого начала установите balance в 0 и пройдите от начала до последнего символа.
Прибавьте 1 для ( и вычтите 1 для ).
Если balance меньше 0, остановитесь для этого начала. Если он равен 0, обновите best, используя длину отрезка end - start + 1.
Верните best.

def longestValidParentheses(s):
    best = 0
    for start in range(len(s)):
        balance = 0
        for end in range(start, len(s)):
            balance += 1 if s[end] == "(" else -1
            if balance < 0:
                # A ')' without a partner: no longer run starts here
                break
            if balance == 0:
                best = max(best, end - start + 1)
    return best

Стек индексов с маркером основания

Идея

Отслеживать совпадающие скобки с помощью стека уже знакомо: поместите каждую ( в стек и извлекайте по одной для каждой ). Здесь также нужны длины, поэтому помещайте в стек индексы и оставляйте внизу стека ещё один индекс: базу — позицию непосредственно перед текущей последовательностью. В начале ещё ничего не прочитано, поэтому база равна -1.

При ( поместите её индекс в стек. При ) извлеките элемент. Возможны два случая. Если стек теперь пуст, значит, вы извлекли базу, поэтому этой ) нечего закрывать. Ни одна правильно сформированная подстрока не может содержать её, и она становится новой базой: поместите её индекс в стек. В противном случае индекс, оставшийся наверху стека, — это последний символ перед последовательностью, заканчивающейся на i: либо незакрытая (, либо база. Всё после него до i включительно образует совпадающую последовательность, и она не может простираться левее, поэтому её длина равна i - top.

Вот пример для ())((()):

i = 0, (: поместите 0 в стек. Стек [-1, 0].
i = 1, ): извлеките 0. Наверху -1, значит, длина последовательности равна 1 - (-1) = 2.
i = 2, ): извлеките -1, и стек опустеет. У этой ) нет пары, поэтому поместите 2 в стек как новую базу. Стек [2].
i = 3, 4, 5, три (: поместите их индексы в стек. Стек [2, 3, 4, 5].
i = 6, ): извлеките 5. Наверху 4, значит, длина последовательности равна 6 - 4 = 2.
i = 7, ): извлеките 4. Наверху 3, значит, длина последовательности равна 7 - 3 = 4 — это и есть ответ.

Именно база позволяет объединять соприкасающиеся части. Для ()(()) длина первой пары равна 1 - (-1) = 2, а последняя ) извлекает индекс 2 и снова находит наверху -1, поэтому длина равна 5 - (-1) = 6. Если бы мы считали длину от соответствующей (, получилось бы 4, и начальная () не учлась бы. Каждый индекс помещается в стек и извлекается из него не более одного раза, поэтому проход выполняется за O(n), а стек может содержать до n+1 индексов.

Алгоритм

Начните со стека, содержащего -1, и установите best в 0.
Для каждого индекса i добавьте i в стек, если s[i] — это (.
Если это ), выполните извлечение из стека один раз.
Если теперь стек пуст, добавьте i как новую базу. В противном случае обновите best, используя i - top.
Верните best.

def longestValidParentheses(s):
    # The bottom of the stack is the index just before the current run
    stack = [-1]
    best = 0
    for i, ch in enumerate(s):
        if ch == "(":
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                # This ')' has no partner: it becomes the new base
                stack.append(i)
            else:
                best = max(best, i - stack[-1])
    return best

Подсчитайте открывающие и закрывающие элементы за два прохода

Идея

Стек всегда лишь показывает, где начался текущий отрезок. То же самое могут делать два счётчика. Идите слева направо, считая opens и closes с момента последнего сброса. Когда они равны, всё с момента сброса корректно, а длина равна 2 × closes. Когда closes становится больше, у ) нет пары — в этот же момент стек теряет свою опору, поэтому сбросьте оба счётчика в 0.

Одного прохода недостаточно. Незакрытая ( навсегда оставляет opens больше, и счётчики больше не сравняются. Для (() левый проход заканчивается с 2 открывающими и 1 закрывающей скобкой и ничего не сообщает, хотя () находится прямо здесь. Поэтому пройдите строку ещё раз, справа налево, поменяв роли счётчиков местами: выполняйте сброс, когда opens становится больше. При чтении в обратном направлении (() даёт закрывающую скобку, затем открывающую (счётчики равны: длина 2), затем открывающую скобку, которая приводит к сбросу. Ответ — большее из значений, полученных за два прохода.

Почему два прохода находят каждый такой отрезок: самый длинный отрезок ограничен символами, которые невозможно сопоставить, или концами строки. Если его левая граница — лишняя ) или начало строки, левый проход выполняет сброс именно там, где начинается отрезок, и обнаруживает равенство счётчиков в месте его окончания. Если его левая граница — лишняя (, его правая граница не может быть ), потому что эта ) закрыла бы лишнюю (, и отрезок был бы длиннее. Значит, правая граница — лишняя ( или конец строки, и правый проход находит отрезок тем же способом. Каждый проход читает строку один раз, используя два целых числа, поэтому время выполнения составляет O(n), а дополнительная память — O(1).

Алгоритм

Установи best в значение 0, а opens и closes — в значение 0.
Проходи слева направо, подсчитывая каждый символ. Когда счётчики равны, обновляй best, присваивая ему 2 × closes. Когда значение closes становится больше, сбрасывай оба счётчика в 0.
Сбрось оба счётчика, затем пройди справа налево тем же способом, за исключением того, что сбрасывать счётчики нужно, когда значение opens становится больше.
Верни best.

def longestValidParentheses(s):
    best = 0

    # Left to right: more ')' than '(' ends every run that started earlier
    opens = closes = 0
    for ch in s:
        if ch == "(":
            opens += 1
        else:
            closes += 1
        if opens == closes:
            best = max(best, 2 * closes)
        elif closes > opens:
            opens = closes = 0

    # Right to left: catches the runs that an unmatched '(' hid from the first pass
    opens = closes = 0
    for ch in reversed(s):
        if ch == "(":
            opens += 1
        else:
            closes += 1
        if opens == closes:
            best = max(best, 2 * opens)
        elif opens > closes:
            opens = closes = 0

    return best

Ловушки и крайние случаи

Большинство неправильных ответов либо считают правильные пары не в тех местах, либо теряют начало последовательности.

Подсчёт совпадающих пар во всей строке. В ())((()) 3 пары, но они не все расположены подряд, поэтому ответ — 4, а не 6.
Измерение последовательности от соответствующей ей (. В ()(()) последняя ) соответствует индексу 2, что даёт 4 и упускает начальную (). Измеряйте от индекса, оставшегося в стеке после извлечения элемента.
Начало с пустым стеком. Тогда для первой ) в ()) не с чем сравнивать, а несоответствующая ) извлекает элемент из пустого стека. Базовое значение -1 решает обе проблемы.
Выполнение подсчётов только в одном направлении. Для (() обход слева направо возвращает 0, а для ()) обход справа налево возвращает 0; в обоих случаях ответ — 2.
Сброс счётчиков, когда они равны. Равные счётчики означают, что последовательность всё ещё может расти, как в ()(); сбрасывайте счётчики, только когда одна сторона начинает преобладать.
В Lua и R позиции начинаются с 1, поэтому первое базовое значение — 0, а не -1.

Частые вопросы3

Какова временная сложность задачи «Самая длинная правильная скобочная последовательность»?

И решение с использованием стека, и решение с двумя проходами и счётчиками считывают каждый символ постоянное число раз, поэтому работают за время O(n). В худшем случае стек требует O(n) памяти, например для строки, состоящей только из (, тогда как счётчикам нужно O(1). Перебор каждого возможного начала занимает O(n²).

Почему стек начинается с -1?

Длина последовательности равна текущему индексу минус индекс непосредственно перед её началом. Для последовательности, начинающейся с индекса 0, этот предыдущий индекс равен -1 — на один шаг раньше строки. Если сначала добавить -1, стек никогда не будет пустым, когда совпадающая ) вычисляет длину, а когда несовпадающая ) извлекает его из стека, эта ) становится новой базой.

Существует ли решение задачи «Самая длинная правильная скобочная последовательность» с помощью динамического программирования?

Да. Пусть end[i] — длина самой длинной корректной подстроки, заканчивающейся на индексе i; она равна 0, когда s[i] — это (. Если s[i-1] — это (, то end[i] = end[i-2] + 2. Если это ), рассмотрим j = i - end[i-1] - 1 — символ перед последовательностью, заканчивающейся на i-1: когда s[j] — это (, он обрамляет эту последовательность, и end[i] = end[i-1] + 2 + end[j-1], где последнее слагаемое добавляет последовательность, примыкающую к ней слева. Ответ — наибольшее значение end[i]; время работы и объём памяти составляют O(n).

def longestValidParentheses(s):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

s = "()(())"

Ожидаемый вывод

Longest Valid Parentheses

Функция

Ограничения

Примеры

Подсказки

Решение

Постройте подстроку от каждой начальной позиции

Стек индексов с маркером основания

Подсчитайте открывающие и закрывающие элементы за два прохода

Ловушки и крайние случаи

Частые вопросы3

Похожие задачи