Given a string of parentheses, add the fewest characters needed so every opening parenthesis has a matching closing parenthesis and the final string is valid.
You are given a string s containing only the characters '(' and ')'.
In one move, you may add a parenthesis character at any position in the string.
Return the minimum number of characters that must be added so that the resulting string is a valid parentheses string.
A parentheses string is valid when:
'(' has a matching ')', andCompute the smallest number of insertions needed to make the string balanced.
s consisting only of '(' and ')'.1 <= s.lengths contains only '(' and ')'Example 1
Input
s = "())"
Output
1
Explanation
The string has one extra closing parenthesis. Adding one '(' at the beginning makes it valid: "(())".
Example 2
Input
s = "(("Output
2
Explanation
Both opening parentheses are unmatched, so two closing parentheses must be added: "(())".
Example 3
Input
s = "()))(("Output
4
Explanation
Two insertions are needed for the extra closing parentheses and two more are needed to match the remaining opening parentheses.
Premium problem context
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.