553. Minimum Add to Make Parentheses Valid
A parentheses string is valid when, reading left to right, the running count of ( never falls behind the count of ), and the two counts end up equal. So (()) and ()() are valid, while )( and ((( are not.
You receive a string s containing only the characters ( and ). In one move you may insert a single ( or ) at any position of the string. Return the minimum number of insertions that makes s valid.
Can you decide the answer in one scan, without ever building the repaired string?
Example 1:
Input: s = "())"
Output: 1
Explanation: The first two characters already match. The final ')' has no partner, so one '(' must be inserted somewhere before it.
Example 2:
Input: s = "((("
Output: 3
Explanation: None of the three '(' characters is ever closed, so each one needs its own inserted ')'.
Constraints:
- 1 ≤ s.length ≤ 1000
- s[i] is '(' or ')'
Hints:
Scan left to right and keep a counter of how many '(' are currently waiting for a partner. What are the only two things a ')' can do to that counter?
A ')' that arrives while nothing is open can never be repaired by later characters — it needs an insertion, so count it the moment you see it. When the scan ends, every '(' still waiting also needs one insertion. The answer is the sum of those two counts.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "())"
Expected output: 1