DSA problem
Minimum Add to Make Parentheses Valid
A parentheses string is valid if and only if it is empty, can be written as AB where A and B are valid strings, or can be written as (A) where A is a valid string. Given a parentheses string s, return the minimum number of parentheses you must add — at any positions — to make the resulting string valid.
A balanced parentheses string requires that, scanning left to right, the number of ) never exceeds the number of ( seen so far, and the totals at the end match. Any violation must be repaired by inserting a parenthesis somewhere. The question is how many such repairs are mandatory in the best case.
The greedy solution scans the string with two counters: open (the number of currently unmatched () and close (the number of unmatched ) discovered so far). For every ( we increment open. For every ) we try to cancel one open: if open > 0, decrement it; otherwise increment close because no opener is available, so this ) is permanently unmatched.
At the end the answer is open + close: every leftover ( needs a matching ) to its right and every leftover ) needs a matching ( to its left. The greedy is optimal because each unmatched parenthesis must be paired with an insertion — there is no shared repair across two violations. Time complexity is O(n) with O(1) extra space.
Examples
s = "())"1s = "((("3s = "()()"0Constraints
- 1 <= s.length <= 1000
- s[i] is either '(' or ')'.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.