Formatted question description: https://leetcode.ca/all/1541.html

1541. Minimum Insertions to Balance a Parentheses String (Medium)

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^5
  • s consists of '(' and ')' only.

Related Topics:
String, Stack

Solution 1.

left and right represents the counts of currently unmatched left and right parenthesis respectively.

// OJ: https://leetcode.com/problems/minimum-insertions-to-balance-a-parentheses-string/

// 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 == '(') {
                ++left;
                if (right) { // Unmatched right, reset it with a matching left parenthesis.
                    right = 0;
                    --left;
                    ++ans;
                }
            } else {
                ++right;
                if (left == 0) { // Make sure we always have a left parenthesis to match right parenthesis.
                    left = 1;
                    ++ans;
                }
                if (right == 2) { // When `right` equals `2`, reset it to `0` with a matching left parenthesis, if any.
                    right = 0;
                    if (left) --left;
                    else ++ans;
                }
            }
        }
        return ans + left * 2 - right;
    }
};

Or

// OJ: https://leetcode.com/problems/minimum-insertions-to-balance-a-parentheses-string/

// Time: O(N)
// Space: O(1)
class Solution {
public:
    int minInsertions(string s) {
        int left = 0, right = 0, ans = 0;
        for (int i = 0; i <= s.size(); ++i) {
            if (i == s.size() || s[i] == '(') {
                if (right) {
                    if (left) {
                        --left;
                        ++ans;
                    } else ans += 2;
                    right = 0;
                }
                if (i < s.size()) ++left;
            } else if (++right == 2) {
                if (left) --left;
                else ++ans;
                right = 0;
            }
        }
        return ans + 2 * left;
    }
};

Solution 2.

right represents the number of right parenthesis we need.

// OJ: https://leetcode.com/problems/minimum-insertions-to-balance-a-parentheses-string/

// 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 ans = 0, right = 0;
        for (char c : s) {
            if (c == '(') {
                if (right % 2) { // we need odd number right parenthesis, provide one right parenthesis to make `right` even.
                    --right;
                    ++ans;
                }
                right += 2; // Need to right parenthesis to match this left parenthesis
            } else {
                --right;
                if (right < 0) { // need to add a left parenthesis
                    right += 2;
                    ++ans;
                }
            }
        }
        return ans + right;
    }
};

Java

class Solution {
    public int minInsertions(String s) {
        int insertions = 0;
        int leftCount = 0;
        int length = s.length();
        int index = 0;
        while (index < length) {
            char c = s.charAt(index);
            if (c == '(') {
                leftCount++;
                index++;
            } else {
                if (leftCount == 0)
                    insertions++;
                else
                    leftCount--;
                if (index == length - 1 || s.charAt(index + 1) != ')') {
                    insertions++;
                    index++;
                } else
                    index += 2;
            }
        }
        insertions += leftCount * 2;
        return insertions;
    }
}

All Problems

All Solutions