5314. Минимальное удаление скобок для валидности
Medium
3 решили
Дана строка
Нужно удалить как можно меньше скобок так, чтобы оставшаяся строка стала правильной: в любом префиксе закрывающих скобок не больше, чем открывающих, а в конце их поровну. Буквы трогать нельзя — они остаются на своих местах (относительно друг друга).
Верните любую такую строку. Если подходящих несколько, достаточно одной минимальной длины. Если все скобки лишние — верните строку только из букв (она может быть пустой).
s из строчных латинских букв и скобок ( и ).Нужно удалить как можно меньше скобок так, чтобы оставшаяся строка стала правильной: в любом префиксе закрывающих скобок не больше, чем открывающих, а в конце их поровну. Буквы трогать нельзя — они остаются на своих местах (относительно друг друга).
Верните любую такую строку. Если подходящих несколько, достаточно одной минимальной длины. Если все скобки лишние — верните строку только из букв (она может быть пустой).
Примеры:
Вход:
zed(a(b)c)de)
Выход:
zed(a(b)c)de
Объяснение: В конце лишняя закрывающая скобка: внутри уже всё парно. Удаляем только её → zed(a(b)c)de.
Вход:
a)b(c)d
Выход:
ab(c)d
Объяснение: Первая ')' появляется, когда ещё не было '('. Её нужно убрать. Дальше (c) уже парно. Остаётся ab(c)d.
Вход:
))((
Выход:
""
Объяснение: Две закрывающие в начале не к чему привязать, две открывающие в конце так и остаются без пары. Все четыре скобки лишние → пустая строка.
Ограничения:
0 <= s.length <= 10^5
s состоит из '(' , ')' и строчных английских букв
Решите эту задачу в браузере
Создайте бесплатный аккаунт — редактор Python, Java, JavaScript и Go, проверка на тестах за секунды.
Комментарии (0)
Зарегистрируйтесь или войдите, чтобы оставить комментарий
Пока нет комментариев. Будьте первым!