Correction de la séquence de parenthèses
Étant donné une chaîne
s composée de parenthèses ouvrantes et fermantes, vous êtes autorisé à transformer certaines parenthèses ouvrantes en fermantes (et inversement). Quel est le nombre minimal d’opérations à effectuer pour obtenir une séquence de parenthèses valide ?Entrée
La seule ligne de l’entrée contient la chaîne
s (1 ≤ |s| ≤ ). Il est garanti que la longueur de s est paire.Sortie
Le programme doit afficher le nombre minimal de modifications nécessaires afin de rendre la séquence valide.
Exemples
Entrée | Sortie |
()(( | 1 |
)( | 2 |
()() | 0 |
((() | 1 |
Explications
- ()(( → ()() ⇒ 1 modification
- )( → () ⇒ 2 modifications
- ()() ⇒ aucune modification nécessaire
- ((() → ()() ⇒ 2 modifications
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB