Самый длинный правильный фрагмент скобок

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

Правильная скобочная последовательность из квадратных скобок строится по правилам:

• пустая строка — правильная;
• если A — правильная, то [A] — правильная;
• если A и B — правильные, то AB — правильная.

Нужно найти максимальную длину (в символах) среди всех подстрок исходной строки, которые являются правильными.

Формат ввода

Одна строка s, состоящая только из символов [ и ].

Формат вывода

Одно целое число — максимальная длина правильной подстроки.

Ограничения

• 1 ≤ |s| ≤ 8000

Пример

Ввод:

[]][][[]]

Вывод:

6

(Например, подстрока [][[]] имеет длину 6 и является правильной.)

Главная трудность — правильный фрагмент может состоять из нескольких частей, например [][], поэтому недостаточно искать только пары соседних скобок. Удобнее идти слева направо и для каждой закрывающей ] понимать, как далеко влево тянется корректная подстрока.

Стек будет хранить индексы: незакрытые [ и одну опорную позицию перед возможным началом фрагмента. Сначала кладём в него -1. Это граница перед строкой: благодаря ей правильный фрагмент, начинающийся с индекса 0, тоже легко измерить.

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

Например, после лишней ] все фрагменты через неё невозможны: именно поэтому нужно запомнить её индекс, а не просто очистить стек.

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

Частая ошибка — хранить в стеке только количество открывающих скобок. Тогда нельзя узнать длину фрагмента и правильно «обнулиться» после лишней ].