Всем привет!
Сегодня продолжаем одновременно 2 начинания: решать сложные задачи и решать задачи на валидные скобочные последовательности 🙂
Как я уже говорил ранее, классическая задача на валидацию скобочной последовательности считается легкой только из-за их мейнстримности: это чуть ли не первая задача, которую решают на алгоритмах, когда проходят стек. А как часто она попадается на интервью, страшно представить.
Но, на самом деле, эта задача не из простых и, стоит хоть немного отойти от классической формулировки, и из легкой она превращается в сложную. Так и в сегодняшней вариации — даже несмотря на то, что оптимальное решение использует все тот же самый стек (да и алгоритм в итоге очень несложный), догадался я до него не с первого раза.
Сложность: 🤬 Сложная
ℹ️ Описание
Напишите функцию для поиска самой длинной подстроки, являющейся правильной скобочной последовательностью.
⚠️ Ограничения
— Длина каждой строки от 0 до 30 000 символов
— Строка состоит из символов '(' и ')'
1️⃣ Пример
Входные данные
s := "(()"
Ответ
2
Самая длинная правильная скобочная последовательность —
().2️⃣ Пример
Входные данные
s := ")()())"
Ответ
4
Самая длинная правильная скобочная последовательность -
()().3️⃣ Пример
Входные данные
s := ""
Ответ
0
✅ Решение
Можно попробовать пойти с помощью брутфорса — взять всю строку (как самую длинную возможную подстроку) и проверить её на валидность. После уменьшить длину подстроки на единицу и проверить на валидность 2 возможные подстроки длиной n-1. Потом ещё на единицу и проверить три возможные подстроки длиной n-2. И так далее, пока не наткнёмся на первую валидную подстроку. Но такое решение будет слишком долгим — на LeetCode вы даже не сможете пройти все тест-кейсы из-за таймаута.
Чтобы найти более оптимальное решение, можно переформулировать задачу: самая длинная подстрока с валидной скобочной последовательностью — это максимальное расстояние между двумя невалидными подстроками. Осталось придумать, как с помощью стека мы можем вырезать все валидные подстроки из оригинальной строки, и задача будет решена 🙂
Посмотреть реализацию и объяснения в блоге.
#stack #hard