Minimum Insertions to Balance a Parentheses String Solution
Minimum Insertions to Balance a Parentheses String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Insertions to Balance a Parentheses String is a medium coding problem on strings, greedy and stack, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Strings, Greedy, Stack
- Asked at: Amazon, Google
- 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
In this problem a parentheses string is balanced when every '(' is matched by two consecutive '))', in that order.
Given a string s of '(' and ')', you may insert either bracket anywhere. Return the minimum number of insertions needed to make s balanced.
Example 1
Input: s = "(()))"
Output: 1
Explanation: The inner "(" is closed by "))" but the outer one is one ")" short.
Example 2
Input: s = "())"
Output: 0
Example 3
Input: s = "))())("
Output: 3
Constraints
1 <= s.length <= 40s consists of '(' and ')'.
Hints for Minimum Insertions to Balance a Parentheses String
Hint 1
Track
need, the number of)still owed. Each(adds 2 to it.Hint 2
If
needever turns odd when a(arrives, the previous group was left with a single)— insert one to square it up.Hint 3
A
)with nothing owed needs a(inserted before it; whatever is still owed at the end is inserted at the end.
How to solve Minimum Insertions to Balance a Parentheses String
Track need, the number of ) still owed. ( adds 2; if that makes need odd, a lone ) was left dangling — insert one. A ) with nothing owed needs a ( inserted before it.
Approach
- On
(:need += 2; ifneedis odd,res += 1,need -= 1. - On
):need -= 1; ifneed < 0,res += 1andneed = 1. - Return
res + need.
Why it works
Each ( must be followed by exactly two ); an odd need when a new ( starts means the previous group had a single ), which must be completed before the new group. A ) with no open group requires an inserted (, after which one more ) is still owed.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Whatever is owed at the end is appended, not forgotten.
Reference solution
Python
def minInsertions(s: str) -> int:
res = 0
need = 0
for ch in s:
if ch == "(":
need += 2
if need % 2 == 1:
res += 1
need -= 1
else:
need -= 1
if need < 0:
res += 1
need = 1
return res + needJava
public static int minInsertions(String s) {
int res = 0, need = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
need += 2;
if (need % 2 == 1) {
res++;
need--;
}
} else {
need--;
if (need < 0) {
res++;
need = 1;
}
}
}
return res + need;
}C++
int minInsertions(string s) {
int res = 0, need = 0;
for (char c : s) {
if (c == '(') {
need += 2;
if (need % 2 == 1) {
res++;
need--;
}
} else {
need--;
if (need < 0) {
res++;
need = 1;
}
}
}
return res + need;
}JavaScript
var minInsertions = function(s) {
let res = 0;
let need = 0;
for (let i = 0; i < s.length; i++) {
if (s.charAt(i) === "(") {
need += 2;
if (need % 2 === 1) {
res++;
need--;
}
} else {
need--;
if (need < 0) {
res++;
need = 1;
}
}
}
return res + need;
};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