SOLVE
LATER
Given a string S
of '('
and ')'
parentheses, we add the minimum number of parentheses ( '('
or ')'
, and in any positions ) so that the resulting parentheses string is valid.
Formally, a parentheses string is valid if and only if:
AB
(A
concatenated with B
), where A
and B
are valid strings, or(A)
, where A
is a valid string.Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid.
The given string can be balanced to "((()))(())", requiring 4 more paranthesis minimum.