Minimum Add to Make Parentheses Valid
Medium · Greedy · String · Stack · Greedy
Problem
A string of parentheses is valid when it is empty, when it is two valid strings written one after the other (AB), or when it is a valid string wrapped in a pair ((A)).
You are given a string s made of '(' and ')'. In one move you may insert a single '(' or ')' at any position. Return the fewest moves that make s valid.
Examples
Input: s = "())" Output: 1
Insert one ( before the last ), or anywhere before it.
Input: s = ")))("
Output: 4Three ) have nothing to close and one ( is never closed: four insertions.
Input: s = "(()())" Output: 0
Every ( is closed in order, so no move is needed.
Constraints
- 1 <= len(s) <= 1000
- s[i] is '(' or ')'
Approaches
- Delete matched pairs until none are left — time O(n²), space O(n)
Follow-up
What if you may only delete characters, and must return one valid string of the greatest length? The same scan finds which ) are unmatched, and a scan from the right finds which ( are; deleting exactly those gives a longest valid result, and the number deleted equals this problem’s answer.
Related problems
Start free on Cariara · Coding problems · System design studio
