Given a parentheses string s containing only the characters '(' and ')'. A parentheses string is balanced if:
- Any left parenthesis
'('must have a corresponding two consecutive right parenthesis'))'. - Left parenthesis
'('must go before the corresponding two consecutive right parenthesis'))'.
In other words, we treat '(' as openning parenthesis and '))' as closing parenthesis.
For example, "())", "())(())))" and "(())())))" are balanced, ")()", "()))" and "(()))" are not balanced.
You can insert the characters '(' and ')' at any position of the string to balance it if needed.
Return the minimum number of insertions needed to make s balanced.
Example 1:
Input: s = "(()))"
Output: 1
Explanation: The second '(' has two matching '))', but the first '(' has only ')' matching. We need to to add one more ')' at the end of the string to be "(())))" which is balanced.
Example 2:
Input: s = "())" Output: 0 Explanation: The string is already balanced.
Example 3:
Input: s = "))())("
Output: 3
Explanation: Add '(' to match the first '))', Add '))' to match the last '('.
Example 4:
Input: s = "(((((("
Output: 12
Explanation: Add 12 ')' to balance the string.
Example 5:
Input: s = ")))))))"
Output: 5
Explanation: Add 4 '(' at the beginning of the string and one ')' at the end. The string becomes "(((())))))))".
Constraints:
1 <= s.length <= 10^5sconsists of'('and')'only.
Companies:
Facebook, Apple, LinkedIn
Related Topics:
String, Stack, Greedy
Similar Questions:
left and right represents the counts of currently unmatched left and right parenthesis respectively.
The following implementation simply discuss different cases we can meet.
// OJ: https://leetcode.com/problems/minimum-insertions-to-balance-a-parentheses-string/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
int minInsertions(string s) {
int left = 0, right = 0, ans = 0;
for (char c : s) {
if (c == '(') {
if (right) { // when we see ( and there is still a ) left
if (left) { // If we have ( balance, use it and add a )
--left;
++ans; // add )
} else ans += 2; // otherwise, add a ( and a )
right = 0; // clear the )
}
++left;
} else {
++right;
if (left) {
if (right == 2) { // if we have ( balance and 2 )s, clear this pair
right = 0;
--left;
}
} else { // if there is no ( balance, we add a (
++ans;
++left;
}
}
}
if (left) { // in the end, if we still have ( balance
ans += 2 * left - right; // add )s
} else {
ans += 2 * right; // add one ( if there is ) balance (must be 1)
}
return ans;
}
};Or
- Whenever we see a
)and we don't have(available, we add a(at this moment. This simplify the cases to consider because it makes sure we always have enough(to cover). - Always reset
)whenever we have two)s.
// OJ: https://leetcode.com/problems/minimum-insertions-to-balance-a-parentheses-string/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
int minInsertions(string s) {
int left = 0, right = 0, ans = 0;
for (char c : s) {
if (c == '(') {
if (right) { // Must be a single unmatched `)`. Clear it with a `(`.
right = 0;
--left;
++ans; // add a `)`
}
++left;
} else {
++right;
if (left == 0) { // We must add a `(` to match this `)`. This makes sure that if we have an unmatched `)`, there must be at least one `(`, simplifying the cases to consider.
left = 1;
++ans; // add one `(`
}
if (right == 2) { // We always reset `)` whenever we have two `)`s.
right = 0;
--left;
}
}
}
return ans + left * 2 - right;
}
};Or
- Always reset
)whenever we have two)s. - Since we don't add
(early (when we see a)without any available(), we need moreif (left)checks later.
// OJ: https://leetcode.com/problems/minimum-insertions-to-balance-a-parentheses-string/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
int minInsertions(string s) {
int left = 0, right = 0, ans = 0, N = s.size();
for (int i = 0; i <= N; ++i) {
if (i == N || s[i] == '(') {
if (right) { // Need to clear this single unmatched `)`.
if (left) { // If we have `(` available, use it
--left;
++ans; // need to add a single `)`
} else ans += 2; // need to add a `(` and a `)`.
right = 0;
}
if (i < N) ++left;
} else if (++right == 2) { // We always reset `)` whenever we have two `)`s.
if (left) --left;
else ++ans; // add a `(`
right = 0;
}
}
return ans + 2 * left;
}
};Or
- We don't even clear
)when we have two)s. We clear)when we see(or reached end of string.
// OJ: https://leetcode.com/problems/minimum-insertions-to-balance-a-parentheses-string/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
int minInsertions(string s) {
int left = 0, right = 0, ans = 0, N = s.size();
for (int i = 0; i <= N; ++i) {
if (i == N || s[i] == '(') {
if (right % 2) ++ans, ++right; // if we have odd `)` balance, add one `)` to make it even
left -= right / 2;
right = 0;
if (left < 0) {
ans -= left;
left = 0;
}
if (i < N) ++left;
} else ++right;
}
return ans + 2 * left;
}
};right represents the number of right parenthesis we need.
// OJ: https://leetcode.com/problems/minimum-insertions-to-balance-a-parentheses-string/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
// Ref: https://leetcode.com/problems/minimum-insertions-to-balance-a-parentheses-string/discuss/780199/JavaC%2B%2BPython-Straight-Forward-One-Pass
class Solution {
public:
int minInsertions(string s) {
int right = 0, ans = 0;
for (char c : s) {
if (c == '(') {
if (right % 2) { // if we have odd `)` needed, we must clear right now
--right;
++ans; // add one `)`
}
right += 2;
} else {
if (right) --right;
else {
right = 1;
++ans; // add a `(`
}
}
}
return ans + right;
}
};