Arreglar la secuencia de paréntesis
Dado un string
s compuesto de paréntesis de apertura y cierre, se permite cambiar algunos paréntesis de apertura a paréntesis de cierre y algunos paréntesis de cierre a paréntesis de apertura. ¿Cuál es el mínimo número de operaciones necesarias para lograr una secuencia de paréntesis válida?Entrada
La única línea de la entrada contiene el string
s (1 ≤ |s| ≤ ). Se garantiza que la longitud de s sea par.Salida
El programa debe imprimir la menor cantidad de modificaciones necesarias para que la secuencia sea válida.
Ejemplos
Entrada | Salida |
()(( | 1 |
)( | 2 |
()() | 0 |
((() | 1 |
Explicación
- ()(( → ()() ⇒ 1 modificación
- )( → () ⇒ 2 modificaciones
- ()() ⇒ no se necesitan modificaciones
- ((() → ()() ⇒ 2 modificaciones
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB