Longest Valid Parentheses: стек индексов, ДП и два прохода за O(1) памяти
Разбор LeetCode 32: самая длинная правильная скобочная подстрока тремя способами — стек индексов, динамика dp[i] и два прохода со счётчиками за O(1) памяти. Трассировки, код и типичные ошибки.
Коротко
| Параметр | Значение |
|---|---|
| Задача | LeetCode 32 Longest Valid Parentheses, уровень Hard |
| Наивно | перебор всех начал с балансом — |
| Стек индексов | на дне стека лежит «стенка» — индекс перед текущим валидным куском; времени и памяти |
| ДП | dp[i] — длина валидной подстроки, которая заканчивается в i; / |
| Два прохода | счётчики left и right слева направо и справа налево; времени, памяти |
Если вы ещё не решали базовую проверку скобок, начните со статьи Валидные скобки: там стек хранит сами скобки. Здесь он хранит индексы, и от этой небольшой разницы зависит всё решение.
Постановка
Дана строка 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
Это времени и памяти. При (ограничение на LeetCode) получается до шагов, и на 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.
Сложность и бонус
Каждый индекс кладётся и снимается не больше одного раза: времени, памяти в худшем случае (строка из одних ().
Если на собеседовании попросят вернуть саму подстроку, а не длину, достаточно запоминать начало: при обновлении максимума start = stack[-1] + 1, а ответ равен s[start:start + best].
Решение 2: динамическое программирование
Состояние
Пусть dp[i] — длина самой длинной правильной подстроки, которая заканчивается ровно в позиции i. Ответ — максимум по всем dp[i]. Правильная строка не может заканчиваться на (, поэтому для таких позиций dp[i] = 0. Интересны только ).
Переходы
Случай 1: s[i - 1] == '(', то есть строка оканчивается на ...(). Пара закрылась сразу, и к ней можно приклеить валидный кусок, который заканчивается в i - 2:
Случай 2: s[i - 1] == ')', строка оканчивается на ...)). Предыдущая ) уже замыкает валидный кусок длиной dp[i - 1]. Перепрыгиваем через него и смотрим на символ перед ним, с индексом j = i - dp[i - 1] - 1. Если там (, это пара для s[i]: вся конструкция имеет вид ( кусок ), и к ней ещё можно приклеить валидный кусок, оканчивающийся в 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 + 0 | 2 |
| 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 отрицательный индекс не упадёт, а молча возьмёт элемент с конца массива, и ответ будет неверным без всякой ошибки.
Сложность: времени и памяти. Асимптотически ДП не лучше стека, но его полезно знать: интервьюер может прямо попросить динамику, а сам приём «длина лучшего ответа, заканчивающегося в 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 возвращает итератор и не копирует строку, так что дополнительная память действительно . Время — , два прохода по строке.
Проверка на "()(()"
Прямой проход: (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, ловушка с лишней ( посередине обработана правильно.
Взгляд через префиксный баланс
Все три решения удобно понимать через одну картинку. Обозначим через баланс префикса длины : число ( минус число ) среди первых символов, . Тогда подстрока s[l..r-1] правильная ровно тогда, когда
Иначе говоря, на графике баланса нужно найти самый длинный горизонтальный отрезок, под который график ни разу не опускается. Для ")()())" баланс равен 0, -1, 0, -1, 0, -1, -2: отрезок от до держится на уровне и не опускается ниже, отсюда ответ 4.
С этой точки зрения стенка в стеке — это позиция, где график впервые опустился на новый минимум, а сброс счётчиков в третьем решении — то же самое событие. Такой язык полезен и в других задачах: например, минимальное число скобок, которое нужно добавить, чтобы строка стала правильной, равно плюс итоговый баланс после этой поправки.
Вариация: несколько типов скобок
Частый 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')
Все строк длины до 12 проходят для каждой из трёх реализаций из статьи. Если на собеседовании есть время, упомяните такой стресс-тест: это хороший сигнал, даже если писать его не попросят.
Сравнение подходов
| Подход | Время | Память | Когда выбирать |
|---|---|---|---|
| Перебор | как стартовая идея и эталон для тестов | ||
| Стек | по умолчанию: короткий код, легко объяснить и восстановить подстроку | ||
| ДП | если просят динамику или нужна длина для каждой позиции | ||
| Два прохода | follow-up «а без дополнительной памяти?» |
Типичные ошибки
- Путать подстроку и подпоследовательность. Если можно выкидывать символы, задача становится простой: ответ равен удвоенному числу пар, которые сопоставит обычный стек. В LeetCode 32 нужен непрерывный кусок.
- Считать длину от парной
(, а не от верха стека. Тогда"()()"даст 2 вместо 4: соседние пары не склеятся. - Не класть стенку
-1в начале. Без неё первая же)сделаетpopиз пустого стека, а длина куска, начинающегося с нуля, посчитается на единицу меньше. - Забыть, что непарная
)становится новой стенкой. Если просто пропустить её, следующий валидный кусок «перешагнёт» через разрыв. - В ДП — потерять
dp[j - 1]или не проверить границыj. Про отрицательные индексы Python см. выше. - В решении со счётчиками — ограничиться одним проходом. Тест
"(()"сразу это покажет. - Обновлять ответ при
left == right, но сбрасывать по>=. Порядок проверок важен: сначала равенство, потом сброс по строгому неравенству.
На собеседовании
Задача часто идёт продолжением к Valid Parentheses: «проверить скобки вы умеете, а теперь найдите самый длинный правильный кусок». Хороший план ответа:
- Уточнить, что речь о подстроке и только о круглых скобках.
- Назвать перебор за с балансом и сразу объяснить, почему он медленный.
- Написать стековое решение со стенкой и прогнать его вслух на
")()())". - На вопрос «а можно без стека?» рассказать про два прохода со счётчиками и объяснить, зачем нужен обратный проход, на примере
"(()".
Динамика обычно звучит как альтернатива: на неё переходят, если интервьюер прямо спрашивает про ДП.
Похожие идеи встречаются и в других задачах. Стек индексов со «стенками» работает в наибольшем прямоугольнике в гистограмме и вообще в задачах на монотонный стек. Баланс скобок как префиксная сумма тесно связан с префиксными суммами и числами Каталана, которые считают правильные скобочные последовательности. А если нужно не найти, а сгенерировать все правильные строки, это задача Generate Parentheses на бэктрекинг.