Minimum Add to Make Parentheses Valid
Problem
s contains only '(' and ')'. In one move
you may insert a single parenthesis anywhere. Return the fewest insertions that turn
s into a balanced string (every opener closed later, in proper nesting).s = "())"Output1s = "((("Output3s = "()))(("Output41 ≤ s.length ≤ 1000 · s[i] is '(' or ')'
Try it yourself
class Solution {
public int minAddToMakeValid(String s) {
}
}
'('. A ')'
with nothing to match needs an inserted '(' right now; whatever openers are
still unmatched at the end each need a ')'.Instinct An optimisation where one obvious local rule (earliest end, farthest reach, biggest first) never needs undoing - commit to it, then try hard to break it.
Memory hack Grab the best bite now and never look back - but only once a counterexample hunt fails to make you regret it.
Open the Greedy guide →Approaches
Brute ForceCancel () Pairs Until None Remain
O(n2)Space O(n)Every adjacent "()" is already a matched pair, so delete them and
repeat until no pair is left. What survives looks like ")))(((" — none
of it can match anything, so each leftover character needs exactly one insertion.
public int minAddToMakeValid(String s) { String cur = s; while (cur.contains("()")) { cur = cur.replace("()", ""); // remove all adjacent matched pairs } return cur.length(); // leftovers look like ")))(((" }
Intuitive picture of matching, but each pass rebuilds the string.
BetterStack of Unmatched Characters
O(n)Space O(n)Push characters onto a stack; when a ')' arrives and the top is a
'(', they cancel and the opener is popped. The stack ends holding exactly the
unmatched characters, and its size is the answer.
public int minAddToMakeValid(String s) { Deque<Character> stack = new ArrayDeque<>(); for (char ch : s.toCharArray()) { if (ch == ')' && !stack.isEmpty() && stack.peek() == '(') { stack.pop(); // matched pair } else { stack.push(ch); } } return stack.size(); }
Linear, and the familiar bracket-matching tool — but the stack is overkill here.
OptimalTwo Counters
O(n)Space O(1)With one bracket type the stack only ever holds "))..)((..(", so two
numbers describe it: open = unmatched '(' so far, and
add = ')' that arrived with no opener. The answer is
add + open.
public int minAddToMakeValid(String s) { int open = 0; // '(' still waiting for a ')' int add = 0; // '(' we must insert for orphan ')' for (char ch : s.toCharArray()) { if (ch == '(') { open++; } else if (open > 0) { open--; } else { add++; } } return add + open; // each leftover '(' needs a ')' }
Dry runs = "())"
- i=0(i))(open=1 add=0
- i=1()i)(match, open=0
- i=2())i(orphan → add=1
- i=3())(iopen=1
- end())(1 + 1 = 2 ✔
Single pass, constant memory — the expected answer.
'(' needs
two closers.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Cancel () Pairs Until None Remain | O(n2) | O(n) |
| Better | Stack of Unmatched Characters | O(n) | O(n) |
| Optimal | Two Counters | O(n) | O(1) |
- Returning
|#'(' - #')'|—")("has equal counts but needs 2. - Letting
opengo negative instead of counting an orphan')'separately. - Forgetting the openers still unmatched at the end of the scan.
- Show
")("early to prove that order matters, not just counts. - Explain why the greedy choice (insert a '(' immediately) is never worse than delaying.
- Contrast with Valid Parentheses: multiple bracket types genuinely need the stack.