Minimum Add to Make Parentheses Valid
A parentheses string is valid if and only if:
- It is the empty string.
- It can be written as
AB(Aconcatenated withB), whereAandBare valid strings. - It can be written as
(A), whereAis a valid string.
You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string.
Return the minimum number of moves required to make s valid.
Example 1
Input
s = "())"Output
1Adding one opening parenthesis makes the string valid.
Example 2
Input
s = "((("Output
3Adding three closing parentheses makes the string valid.
Constraints
- 1 <= s.length <= 1000
- s[i] is either '(' or ')'.