Strings Parentheses and nesting
135. Minimum Add to Make Parentheses Valid
You are given a string s made of ( and ). In one move, you insert a single ( or ) anywhere in
s: at the start, at the end, or between two characters.
Return the fewest moves that make s valid. A string is valid when its parentheses are properly
nested: every ( is closed by a later ), and every ) closes an earlier (.
Example 1
Input: s = "())(()("
3Explanation: The ) at index 2 has nothing open to close, so it needs a ( before it. The ( at indexes 3 and 6
are never closed, so each needs a ) after it. One valid result is ()()(()()).
Example 2
Input: s = "))(("
4Explanation: Every ) comes before every (, so no two of them can pair up. Each one needs a partner of its own,
as in (())(()).
Example 3
Input: s = "(()())"
0Explanation: The string is already valid.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ s.length ≤ 105sholds only the characters(and).
Clarifying questions
What you would ask an interviewer before writing any code.