Исправляем последовательность скобок
Дана строка
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