Longest Valid Parentheses: стек индексов, ДП и два прохода за O(1) памяти

Разбор LeetCode 32: самая длинная правильная скобочная подстрока тремя способами — стек индексов, динамика dp[i] и два прохода со счётчиками за O(1) памяти. Трассировки, код и типичные ошибки.

9 мин чтенияалгоритмы · стек · динамическое программирование · python

Коротко

ПараметрЗначение
ЗадачаLeetCode 32 Longest Valid Parentheses, уровень Hard
Наивноперебор всех начал с балансом — O(n2)O(n^2)
Стек индексовна дне стека лежит «стенка» — индекс перед текущим валидным куском; O(n)O(n) времени и памяти
ДПdp[i] — длина валидной подстроки, которая заканчивается в i; O(n)O(n) / O(n)O(n)
Два проходасчётчики left и right слева направо и справа налево; O(n)O(n) времени, O(1)O(1) памяти

Если вы ещё не решали базовую проверку скобок, начните со статьи Валидные скобки: там стек хранит сами скобки. Здесь он хранит индексы, и от этой небольшой разницы зависит всё решение.

Постановка

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

sОтветПодстрока
"(()"2()
")()())"4()()
""0—
"()(())"6вся
"()(()"2()
"(()))())("4(())

Пример "()(()" полезен как ловушка. Кажется, что «() плюс ()» даёт 4, но между ними стоит лишняя ( с индексом 2, у которой нет пары. Она разрывает строку, и склеить куски нельзя.

Наивное решение: перебор с балансом

Перебираем начало i и идём вправо, поддерживая баланс: +1 на (, -1 на ). Если баланс ушёл в минус, дальше от этого i правильной подстроки уже не будет: лишнюю ) ничто справа не исправит. Если баланс равен нулю, отрезок s[i..j] правильный.

def longest_valid_brute(s: str) -> int: best = 0 for i in range(len(s)): balance = 0 for j in range(i, len(s)): balance += 1 if s[j] == '(' else -1 if balance < 0: break if balance == 0: best = max(best, j - i + 1) return best

Это O(n2)O(n^2) времени и O(1)O(1) памяти. При n=3⋅104n = 3 \cdot 10^4 (ограничение на LeetCode) получается до 4.5⋅1084.5 \cdot 10^8 шагов, и на Python такое решение не уложится в лимит. Но оно пригодится как эталон для проверки быстрых версий, и его стоит проговорить на собеседовании первым.

Заодно этот перебор показывает критерий, на котором стоят все три быстрых решения: отрезок правильный, когда баланс на нём ни разу не уходит в минус и в конце равен нулю.

Решение 1: стек индексов

Идея

В обычной проверке скобок стек хранит открытые скобки. Здесь нам нужна длина, поэтому храним индексы открывающих скобок, которые пока без пары. Кроме них нужен ещё один индекс, «стенка»: позиция символа сразу перед текущим валидным куском. Стенка всегда лежит на дне стека.

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

Почему длина считается от верха стека, а не от индекса парной (? Потому что слева к паре может примыкать уже закрытый валидный кусок. В "()(())" на последней ) парная ( стоит на индексе 2, но слева от неё лежит (), и правильная подстрока начинается с нуля. Закрытые пары из стека уже сняты, поэтому верх стека указывает на ближайшую позицию, которую склеить не получится: незакрытую ( или стенку.

Код

def longest_valid_parentheses(s: str) -> int: stack = [-1] # индекс «стенки» перед текущим валидным отрезком best = 0 for i, ch in enumerate(s): if ch == '(': stack.append(i) else: stack.pop() if not stack: stack.append(i) # непарная ')' — новая стенка else: best = max(best, i - stack[-1]) return best

То же на JavaScript, например для фронтенд-собеседования:

function longestValidParentheses(s) { const stack = [-1] let best = 0 for (let i = 0; i < s.length; i++) { if (s[i] === '(') { stack.push(i) } else { stack.pop() if (stack.length === 0) { stack.push(i) } else { best = Math.max(best, i - stack[stack.length - 1]) } } } return best }

Трассировка на ")()())"

iсимволдействиестекbest
0)pop -1, стек пуст → стенка 0[0]0
1(push 1[0, 1]0
2)pop 1, длина 2 - 0 = 2[0]2
3(push 3[0, 3]2
4)pop 3, длина 4 - 0 = 4[0]4
5)pop 0, стек пуст → стенка 5[5]4

На шаге 4 и видно, зачем нужна стенка: пара (3, 4) склеилась с () слева, потому что от индекса 0 до 4 стек ни разу не запомнил ничего, кроме стенки.

Трассировка на ловушке "()(()"

iсимволстекдлина
0([-1, 0]—
1)[-1]1 - (-1) = 2
2([-1, 2]—
3([-1, 2, 3]—
4)[-1, 2]4 - 2 = 2

Незакрытая ( с индексом 2 так и осталась в стеке и работает как ещё одна стенка. Поэтому последняя пара считается от индекса 2, а не от -1, и ответ получается 2, а не 4.

Сложность и бонус

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

Если на собеседовании попросят вернуть саму подстроку, а не длину, достаточно запоминать начало: при обновлении максимума start = stack[-1] + 1, а ответ равен s[start:start + best].

Решение 2: динамическое программирование

Состояние

Пусть dp[i] — длина самой длинной правильной подстроки, которая заканчивается ровно в позиции i. Ответ — максимум по всем dp[i]. Правильная строка не может заканчиваться на (, поэтому для таких позиций dp[i] = 0. Интересны только ).

Переходы

Случай 1: s[i - 1] == '(', то есть строка оканчивается на ...(). Пара закрылась сразу, и к ней можно приклеить валидный кусок, который заканчивается в i - 2:

dp[i]=dp[i−2]+2dp[i] = dp[i-2] + 2

Случай 2: s[i - 1] == ')', строка оканчивается на ...)). Предыдущая ) уже замыкает валидный кусок длиной dp[i - 1]. Перепрыгиваем через него и смотрим на символ перед ним, с индексом j = i - dp[i - 1] - 1. Если там (, это пара для s[i]: вся конструкция имеет вид ( кусок ), и к ней ещё можно приклеить валидный кусок, оканчивающийся в j - 1:

dp[i]=dp[i−1]+2+dp[j−1]dp[i] = dp[i-1] + 2 + dp[j-1]

Если j < 0 или s[j] == ')', пары нет и dp[i] = 0.

Код

def longest_valid_dp(s: str) -> int: n = len(s) dp = [0] * n # dp[i] — длина валидной подстроки, заканчивающейся в i best = 0 for i in range(1, n): if s[i] != ')': continue if s[i - 1] == '(': dp[i] = 2 + (dp[i - 2] if i >= 2 else 0) else: j = i - dp[i - 1] - 1 # кандидат в пару для s[i] if j >= 0 and s[j] == '(': dp[i] = dp[i - 1] + 2 + (dp[j - 1] if j >= 1 else 0) best = max(best, dp[i]) return best

Разбор на "()(())"

iсимволслучайdp[i]
0(—0
1)s[0] = '(': 2 + 02
2(—0
3(—0
4)s[3] = '(': 2 + dp[2]2
5)j = 5 - 2 - 1 = 2, s[2] = '(': 2 + 2 + dp[1]6

На последнем шаге работают все три слагаемых: внутренний кусок () (dp[4] = 2), новая внешняя пара (+2) и приклеенный слева () (dp[1] = 2).

Самая частая ошибка в этом решении — забыть dp[j - 1]. Тогда на "()(())" выйдет 4 вместо 6. Вторая по частоте — не проверить j >= 0 и j >= 1. В Python отрицательный индекс не упадёт, а молча возьмёт элемент с конца массива, и ответ будет неверным без всякой ошибки.

Сложность: O(n)O(n) времени и O(n)O(n) памяти. Асимптотически ДП не лучше стека, но его полезно знать: интервьюер может прямо попросить динамику, а сам приём «длина лучшего ответа, заканчивающегося в i» встречается часто, например в наибольшей возрастающей подпоследовательности и в алгоритме Кадане.

Решение 3: два прохода со счётчиками, O(1) памяти

Идея

Вернёмся к критерию из перебора: баланс не уходит в минус и в конце равен нулю. Будем идти слева направо и считать left (сколько () и right (сколько )) с момента последнего сброса.

  • left == right: отрезок от точки сброса до i правильный, его длина 2 * right.
  • right > left: появилась лишняя ). Через неё правильная подстрока не пройдёт, поэтому сбрасываем оба счётчика в ноль. Это та же стенка, что и в стековом решении.

Почему одного прохода мало

На строке "(()" счётчики идут так: (1, 0), (2, 0), (2, 1). Равенства ни разу нет, сброса тоже нет, и проход вернёт 0, хотя ответ 2. Беда в лишних (: при движении слева направо они никогда не вызывают сброс, а просто мешают балансу сойтись.

Лекарство — второй проход справа налево с зеркальными правилами: сбрасываемся, когда left > right. Справа налево лишние ( ловятся так же, как лишние ) слева направо. Строка "(()" справа налево читается как ), (, (: после второго символа left == right == 1, длина 2. Найдено.

Почему двух проходов достаточно? Возьмём самую длинную правильную подстроку s[a..b]. Пусть прямой проход в момент a считает от точки сброса r <= a, и на куске s[r..a-1] накоплен перевес d >= 0 открывающих. Внутри s[a..b] баланс не уходит в минус, поэтому сброса там не будет, а в точке b разность счётчиков снова равна d.

  • Если d = 0, прямой проход увидит left == right в точке b и учтёт отрезок s[r..b] длиной не меньше b - a + 1.
  • Если d > 0, в s[r..a-1] есть непарная (. Возьмём самую правую такую, позиция p: между ней и a лежит правильный (возможно, пустой) кусок.

Симметрично для обратного прохода: либо он найдёт отрезок, либо справа от b есть непарная ) в позиции q, и между b и q тоже правильный кусок. Но если сработали оба «либо», то s[p..q] — это ( + правильное + правильное + правильное + ), то есть правильная подстрока длиннее максимальной. Противоречие, значит, хотя бы один из проходов ответ найдёт.

Код

def longest_valid_counters(s: str) -> int: best = 0 left = right = 0 for ch in s: # слева направо if ch == '(': left += 1 else: right += 1 if left == right: best = max(best, 2 * right) elif right > left: left = right = 0 left = right = 0 for ch in reversed(s): # справа налево if ch == '(': left += 1 else: right += 1 if left == right: best = max(best, 2 * left) elif left > right: left = right = 0 return best

reversed(s) в Python возвращает итератор и не копирует строку, так что дополнительная память действительно O(1)O(1). Время — O(n)O(n), два прохода по строке.

Проверка на "()(()"

Прямой проход: (1,0) → (1,1) длина 2 → (2,1) → (3,1) → (3,2). Максимум 2, сбросов не было. Обратный проход: ) → (0,1), ( → (1,1) длина 2, ( → (2,1): left > right, сброс, ) → (0,1), ( → (1,1) длина 2. Максимум 2.

Ответ 2, ловушка с лишней ( посередине обработана правильно.

Взгляд через префиксный баланс

Все три решения удобно понимать через одну картинку. Обозначим через B(k)B(k) баланс префикса длины kk: число ( минус число ) среди первых kk символов, B(0)=0B(0) = 0. Тогда подстрока s[l..r-1] правильная ровно тогда, когда

B(l)=B(r)иB(k)≥B(l) для всех l≤k≤r.B(l) = B(r) \quad \text{и} \quad B(k) \ge B(l) \text{ для всех } l \le k \le r.

Иначе говоря, на графике баланса нужно найти самый длинный горизонтальный отрезок, под который график ни разу не опускается. Для ")()())" баланс равен 0, -1, 0, -1, 0, -1, -2: отрезок от k=1k = 1 до k=5k = 5 держится на уровне −1-1 и не опускается ниже, отсюда ответ 4.

С этой точки зрения стенка в стеке — это позиция, где график впервые опустился на новый минимум, а сброс счётчиков в третьем решении — то же самое событие. Такой язык полезен и в других задачах: например, минимальное число скобок, которое нужно добавить, чтобы строка стала правильной, равно −min⁡B-\min B плюс итоговый баланс после этой поправки.

Вариация: несколько типов скобок

Частый follow-up: «а если в строке есть (), [] и {}?». Решение со счётчиками здесь ломается. Счётчик знает, сколько скобок открыто, но не знает, каких именно, и строку "([)]" посчитает правильной. Динамика тоже требует доработки. А стек индексов переносится почти без изменений: по индексу на вершине всегда можно посмотреть, какая скобка открыта.

PAIRS = {')': '(', ']': '[', '}': '{'} def longest_valid_multi(s: str) -> int: stack = [-1] best = 0 for i, ch in enumerate(s): if ch in '([{': stack.append(i) elif stack[-1] != -1 and s[stack[-1]] == PAIRS[ch]: stack.pop() best = max(best, i - stack[-1]) else: stack.append(i) # непарная закрывающая — стенка return best

Отличие от версии для одного типа в том, что pop делается только при совпадении типа. Любая закрывающая без пары, включая «чужую» (например, ] над открытой (), кладётся в стек как стенка. Старые стенки при этом можно не снимать: они лежат глубже и уже ни на что не влияют.

Обратите внимание на проверку stack[-1] != -1. Без неё на строке, которая начинается с ], выражение s[stack[-1]] превратится в s[-1], то есть в последний символ строки. Если строка кончается на [, код решит, что нашёл пару. Стенки с неотрицательными индексами такой проблемы не создают: там всегда лежит закрывающая скобка, и с открывающей она не совпадёт.

Проверка: "([)]()[]" → 4 (кусок ()[]), "{[()]}]" → 6. Функция сверена с перебором на всех строках из ()[] длины до 8.

Как проверить себя

Три решения легко сверить с перебором на всех строках небольшой длины. Это пять строк кода, и они ловят почти все ошибки с границами:

from itertools import product for n in range(13): for chars in product('()', repeat=n): s = ''.join(chars) expected = longest_valid_brute(s) assert longest_valid_parentheses(s) == expected, s assert longest_valid_dp(s) == expected, s assert longest_valid_counters(s) == expected, s print('ok')

Все 213−1=81912^{13} - 1 = 8191 строк длины до 12 проходят для каждой из трёх реализаций из статьи. Если на собеседовании есть время, упомяните такой стресс-тест: это хороший сигнал, даже если писать его не попросят.

Сравнение подходов

ПодходВремяПамятьКогда выбирать
ПереборO(n2)O(n^2)O(1)O(1)как стартовая идея и эталон для тестов
СтекO(n)O(n)O(n)O(n)по умолчанию: короткий код, легко объяснить и восстановить подстроку
ДПO(n)O(n)O(n)O(n)если просят динамику или нужна длина для каждой позиции
Два проходаO(n)O(n)O(1)O(1)follow-up «а без дополнительной памяти?»

Типичные ошибки

  1. Путать подстроку и подпоследовательность. Если можно выкидывать символы, задача становится простой: ответ равен удвоенному числу пар, которые сопоставит обычный стек. В LeetCode 32 нужен непрерывный кусок.
  2. Считать длину от парной (, а не от верха стека. Тогда "()()" даст 2 вместо 4: соседние пары не склеятся.
  3. Не класть стенку -1 в начале. Без неё первая же ) сделает pop из пустого стека, а длина куска, начинающегося с нуля, посчитается на единицу меньше.
  4. Забыть, что непарная ) становится новой стенкой. Если просто пропустить её, следующий валидный кусок «перешагнёт» через разрыв.
  5. В ДП — потерять dp[j - 1] или не проверить границы j. Про отрицательные индексы Python см. выше.
  6. В решении со счётчиками — ограничиться одним проходом. Тест "(()" сразу это покажет.
  7. Обновлять ответ при left == right, но сбрасывать по >=. Порядок проверок важен: сначала равенство, потом сброс по строгому неравенству.

На собеседовании

Задача часто идёт продолжением к Valid Parentheses: «проверить скобки вы умеете, а теперь найдите самый длинный правильный кусок». Хороший план ответа:

  1. Уточнить, что речь о подстроке и только о круглых скобках.
  2. Назвать перебор за O(n2)O(n^2) с балансом и сразу объяснить, почему он медленный.
  3. Написать стековое решение со стенкой и прогнать его вслух на ")()())".
  4. На вопрос «а можно без стека?» рассказать про два прохода со счётчиками и объяснить, зачем нужен обратный проход, на примере "(()".

Динамика обычно звучит как альтернатива: на неё переходят, если интервьюер прямо спрашивает про ДП.

Похожие идеи встречаются и в других задачах. Стек индексов со «стенками» работает в наибольшем прямоугольнике в гистограмме и вообще в задачах на монотонный стек. Баланс скобок как префиксная сумма тесно связан с префиксными суммами и числами Каталана, которые считают правильные скобочные последовательности. А если нужно не найти, а сгенерировать все правильные строки, это задача Generate Parentheses на бэктрекинг.

Потренироваться в спокойной обстановке

Все задачи