{x}
blog image

Minimum Insertions to Balance a Parentheses String

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 an opening parenthesis and '))' as a 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 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 '('.

 

Constraints:

  • 1 <= s.length <= 105
  • s consists of '(' and ')' only.

Solution Explanation

This problem asks for the minimum number of insertions needed to balance a parentheses string where each opening parenthesis '(' must be matched by two consecutive closing parentheses '))'. The solution uses a greedy approach with a single pass through the string.

Approach

The code iterates through the string, maintaining a variable x to track the number of unmatched opening parentheses.

  • Opening Parenthesis (: Increment x. This represents an opening parenthesis awaiting its closing pair )).

  • Closing Parenthesis ):

    • Consecutive )): If the current character is ')' and the next character is also ')', this represents a complete closing pair. Increment i to skip the next character and continue.

    • Single ): If only a single ')' is found, it means we need to insert either an opening '(' or another closing ')', depending on the current state. Increment ans (the number of insertions). If x is 0 (no unmatched '('), we need to insert an opening '(' before this ')', so increment ans again. Otherwise, decrement x because this ')' matches an existing unmatched opening parenthesis.

  • End of String: After iterating through the string, if x is greater than 0, it means there are unmatched opening parentheses. We need to insert 2 * x closing parentheses to balance them. Add this to ans.

Time and Space Complexity

  • Time Complexity: O(N), where N is the length of the string. The code iterates through the string once.

  • Space Complexity: O(1). The solution uses only a few constant extra variables (ans, x, i, n).

Code Explanation (Python)

The Python code efficiently implements the greedy approach:

class Solution:
    def minInsertions(self, s: str) -> int:
        ans = x = 0  # Initialize the number of insertions and unmatched opening parentheses
        i, n = 0, len(s)  # Initialize the index and length of the string
        while i < n:
            if s[i] == '(':
                x += 1  # Unmatched opening parenthesis
            else:
                if i < n - 1 and s[i + 1] == ')':
                    i += 1  # Skip the next ')' if it's a closing pair
                else:
                    ans += 1  # Insert either '(' or ')' as needed
                if x == 0:
                    ans += 1  # Need to insert '(' because there were no unmatched '('
                else:
                    x -= 1  # Matched an opening parenthesis
            i += 1  # Move to the next character
        ans += x << 1  # Add insertions for remaining unmatched opening parentheses (using bit shift for efficiency)
        return ans

The other languages (Java, C++, Go) follow the same logic and differ only in syntax. The core algorithm remains consistent across all implementations.