A parentheses string is valid if and only if:
- It is the empty string,
- It can be written as
AB
(A
concatenated withB
), whereA
andB
are valid strings, or - It can be written as
(A)
, whereA
is a valid string.
You are given a parentheses string s
. In one move, you can insert a parenthesis at any position of the string.
- For example, if
s = "()))"
, you can insert an opening parenthesis to be"(**(**)))"
or a closing parenthesis to be"())**)**)"
.
Return the minimum number of moves required to make s
valid.
Example 1:
Input: s = "())"
Output: 1
Example 2:
Input: s = "((("
Output: 3
Constraints:
-
1 <= s.length <= 1000
-
s[i]
is either'('
or')'
.
SOLUTION:
class Solution:
def minAddToMakeValid(self, s: str) -> int:
stack = []
ctr = 0
for c in s:
if c == '(':
stack.append('(')
else:
if len(stack) == 0 or stack[-1] != '(':
ctr += 1
else:
stack.pop()
ctr += len(stack)
return ctr
Top comments (0)