Minimum Insertions to Balance a Parentheses String

Medium

Google

1 view

Topics:

StringsGreedy Algorithms

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 '((.

Minimum Insertions to Balance a Parentheses String

Medium

Google

1 view

Topics:

StringsGreedy Algorithms

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 '((.

Solution

Naive Solution

A brute force approach would involve trying all possible insertions of '(' and ')' to balance the string. However, this method is highly inefficient due to the exponential number of possibilities.

Optimal Solution: Greedy Approach

A more efficient solution uses a greedy approach. We iterate through the string and keep track of the balance. When we encounter an unbalanced state, we insert the minimum number of parentheses to correct it.

Algorithm:

Initialize balance = 0 and insertions = 0.
Iterate through the string s:
- If s[i] == '(', increment balance.
- If s[i] == ')':
  - If balance > 0, decrement balance.
  - Else, increment insertions (insert a '(').
  - If next char s[i+1] == ')' then increment i.
  - Else increment insertions (insert a ')' ).
After the loop, if balance > 0, increment insertions by balance * 2 (insert the corresponding '))' pairs).
Return insertions.

Code (Python):

def minInsertions(s: str) -> int:
    balance = 0
    insertions = 0
    i = 0
    while i < len(s):
        if s[i] == '(':           
            balance += 1
            i += 1
        else:
            if balance > 0:
                balance -= 1
                
            else:
                insertions += 1
            
            if i + 1 < len(s) and s[i+1] == ')':
                i += 2
            else:
                insertions += 1
                i += 1

    insertions += balance * 2
    return insertions

Edge Cases:

Empty string: Should return 0.
String with only '(': Need to add '))' pairs.
String with only ')': Need to add '(' before each '))' pair.

Example:

s = "))())(("

First '))': insertions += 1 to add '(', so string becomes (())(("
Next '(': balance = 1
Next ')': balance = 0
Next ')': insertions += 1 to add '(', so string becomes (()()(("
Last '((': balance = 1, then balance = 2.
Finally, insertions += balance * 2 = 4, to add '))))' at the end.
Return insertions = 1 + 1 + 4 = 6

Big(O) Analysis

Time Complexity: O(n), where n is the length of the string, as we iterate through the string once.
Space Complexity: O(1), as we only use a few integer variables.

Solution

Naive Solution

A brute force approach would involve trying all possible insertions of '(' and ')' to balance the string. However, this method is highly inefficient due to the exponential number of possibilities.

Optimal Solution: Greedy Approach

Algorithm:

Initialize balance = 0 and insertions = 0.
Iterate through the string s:
- If s[i] == '(', increment balance.
- If s[i] == ')':
  - If balance > 0, decrement balance.
  - Else, increment insertions (insert a '(').
  - If next char s[i+1] == ')' then increment i.
  - Else increment insertions (insert a ')' ).
After the loop, if balance > 0, increment insertions by balance * 2 (insert the corresponding '))' pairs).
Return insertions.

Code (Python):

def minInsertions(s: str) -> int:
    balance = 0
    insertions = 0
    i = 0
    while i < len(s):
        if s[i] == '(':           
            balance += 1
            i += 1
        else:
            if balance > 0:
                balance -= 1
                
            else:
                insertions += 1
            
            if i + 1 < len(s) and s[i+1] == ')':
                i += 2
            else:
                insertions += 1
                i += 1

    insertions += balance * 2
    return insertions

Edge Cases:

Empty string: Should return 0.
String with only '(': Need to add '))' pairs.
String with only ')': Need to add '(' before each '))' pair.

Example:

s = "))())(("

First '))': insertions += 1 to add '(', so string becomes (())(("
Next '(': balance = 1
Next ')': balance = 0
Next ')': insertions += 1 to add '(', so string becomes (()()(("
Last '((': balance = 1, then balance = 2.
Finally, insertions += balance * 2 = 4, to add '))))' at the end.
Return insertions = 1 + 1 + 4 = 6

Big(O) Analysis

Time Complexity: O(n), where n is the length of the string, as we iterate through the string once.
Space Complexity: O(1), as we only use a few integer variables.