Minimum Add to Make Parentheses Valid — Problem & Solution
Minimum Add to Make Parentheses Valid solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimum Add to Make Parentheses Valid is a medium coding problem on strings, greedy and stack, asked in Amazon, Google and Meta interviews.
- Difficulty: Medium
- Topics: Strings, Greedy, Stack
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A parentheses string is valid if every open bracket has a matching close bracket in the right order.
Given a string s of '(' and ')', you may insert a bracket anywhere. Return the minimum number of insertions needed to make s valid.
Example 1
Input: s = "())"
Output: 1
Example 2
Input: s = "((("
Output: 3
Example 3
Input: s = "()"
Output: 0
Constraints
1 <= s.length <= 40s consists of '(' and ')'.
Hints for Minimum Add to Make Parentheses Valid
Hint 1
Sweep left to right keeping a count of unmatched open brackets.
Hint 2
A
)with no open bracket waiting can never be matched later, so it needs an insertion right away.Hint 3
Whatever open brackets remain at the end each need a
)appended.
How to solve Minimum Add to Make Parentheses Valid
Count unmatched opens as you scan; a ) with none waiting needs an insertion immediately, and every open left at the end needs one too.
Approach
- For
(, incrementopen; for), decrement ifopen > 0, else incrementneeded. - Return
needed + open.
Why it works
An unmatched ) can only be fixed by a ( before it, and each leftover ( by a ) after it; the greedy match never wastes a bracket.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- A stack is unnecessary — only its size matters.
Reference solution
Python
def minAddToMakeValid(s: str) -> int:
open_count = 0
needed = 0
for ch in s:
if ch == "(":
open_count += 1
elif open_count > 0:
open_count -= 1
else:
needed += 1
return needed + open_countJava
public static int minAddToMakeValid(String s) {
int open = 0, needed = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') open++;
else if (open > 0) open--;
else needed++;
}
return needed + open;
}C++
int minAddToMakeValid(string s) {
int open = 0, needed = 0;
for (char c : s) {
if (c == '(') open++;
else if (open > 0) open--;
else needed++;
}
return needed + open;
}JavaScript
var minAddToMakeValid = function(s) {
let open = 0, needed = 0;
for (let i = 0; i < s.length; i++) {
if (s.charAt(i) === "(") open++;
else if (open > 0) open--;
else needed++;
}
return needed + open;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Greedy Algorithms