Исправляем последовательность скобок
Дана строка s, состоящая из открывающих и закрывающих скобок. Разрешается заменить некоторые открывающие скобки на закрывающие и наоборот. Какое минимальное количество таких преобразований необходимо, чтобы получить корректную скобочную последовательность?
Входные данные
В единственной строке задаётся строка s (1 ≤ |s| ≤ ). Гарантируется, что длина s чётна.
Выходные данные
Программа должна вывести минимальное количество изменений, необходимых для преобразования последовательности в корректную.
Примеры
Входные данные | Выходные данные |
|---|---|
()(( | 1 |
)( | 2 |
()() | 0 |
((() | 1 |
Пояснение
()(( → ()() ⇒ 1 изменение
)( → () ⇒ 2 изменения
()() ⇒ изменений не требуется
((() → ()() ⇒ 2 изменения
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB