1541. Minimum Insertions to Balance a Parentheses String


Problem Description

The given problem involves a string s which contains only parentheses – specifically, the characters '(' and ')'. The objective is to make the string balanced according to the following rules:

  • A left parenthesis '(' must be followed by two consecutive right parentheses '))'.
  • The order must be maintained, i.e., for every '(', the corresponding '))' must come after it.

We can add parentheses anywhere in the string to balance it. The task is to find the minimum number of insertions required to balance the string.

Examples of balanced strings as per these rules are: "())", "())(())))", and "(())())))". On the other hand, strings like ")()", "()))", and "(()))" are not balanced as per the rules described.

Intuition

The intuition behind the solution is to iterate through the string, keeping track of how many opening and closing parentheses are needed to balance the string as we go.

We maintain two counters:

  • x: to count the number of opening parentheses '(' we have seen that need right parentheses '))'.
  • ans: to count the number of insertions needed to balance the string.

While iterating through the string:

  • When we encounter an '(', we increment x because we anticipate needing two more ')' to balance it later.
  • When we encounter a ')', we have two cases:
    • If it's followed by another ')', this means we found a pair '))', so we decrement x as we have matched one opening '(' with two closing '))'.
    • If it's not followed by another ')', we have a single ')', so we add one to ans as we need to insert an additional ')' to balance the string, and then decrement x.
  • If x is zero and a closing ')' without a matching '(' is found, we need to insert an opening '(' before it, so we add one to ans.
  • After processing the closing parentheses, if x is greater than zero, it means there are unmatched '(' pending, so we need to add two ')' for each of them. Thus, we increment ans by x shifted to the left by 1 (which is equivalent to multiplying x by 2).

This solution ensures that we make the minimum number of insertions required to balance the string by only adding parentheses when necessary to make the string adhere to the balancing rules.

Solution Approach

The implementation of the solution involves a greedy approach to satisfy the conditions for a balanced parentheses string, as mentioned earlier. The algorithm can be detailed as follows:

  1. Initialize Two Counters: We have two counters ans and x, where ans keeps track of the number of insertions needed and x keeps track of the number of unmatched opening parentheses that are yet to be paired with a closing parentheses.

  2. Iterating Over the String: We iterate over each character in the string using a while loop, indexed by i.

  3. Handling Opening Parentheses '(': When we encounter an opening parenthesis, we increment x by 1, as we need to find or insert two consecutive closing parentheses to balance it.

  4. Handling Closing Parentheses ')':

    • If the current character is a ')', we first check whether it forms a pair with the next character (i.e., if it is followed by another ')'). If yes, we increment i by 1 to skip the next character since we have a complete pair '))', and then we decrement x.
    • If there is no ')' following the current one, we increment ans as we need to insert an additional ')' to have a pair '))'. We then check x: if x is zero (meaning we have an excess of closing parentheses), we increment ans again to insert a '(' before the existing ')'. Otherwise, if x is not zero, we simply decrement x.
  5. Handle Unmatched Opening Parentheses: After the loop, if we still have unmatched opening parentheses (i.e., if x is greater than zero), it means we need to insert two ')' for each. We do this by adding x << 1 (which is equivalent to x * 2) to ans.

  6. Returning the Result: Finally, the ans counter now contains the minimal number of insertions needed to balance the string according to the problem constraints, and we return this value.

The key points in this greedy algorithm are:

  • Efficiently keeping track of the number of parentheses we need to insert.
  • Balancing insertions only when necessary to fulfill the condition that each '(' is followed by two ')'.
  • Using bitwise shift x << 1 as a quick operation to double the x value, which is equivalent to adding two closing parentheses for every unmatched '(' at the end of the iteration.

By following this approach, we can guarantee the minimum number of insertions needed to achieve a balanced string.

💪
Level Up Your
Algo Skills

Example Walkthrough

Consider the string s = "(()))(". We need to go through the string and determine how many insertions are required to make this string balanced according to the rules. Let's walk through the solution step-by-step:

  1. Initialize two counters:

    • ans = 0 (counts the total number of insertions needed)
    • x = 0 (counts the number of open parentheses '(' that need to be paired with closing ones '))')
  2. Iterating over the string:

    • Index i = 0, character s[i] = '(':
      • We increment x because this opening parenthesis needs two closing ones.
      • State after this step: ans = 0, x = 1
    • Index i = 1, character s[i] = '(':
      • We increment x again for another unmatched opening parenthesis.
      • State after this step: ans = 0, x = 2
    • Index i = 2, character s[i] = ')':
      • This right parenthesis could be paired with one from the previous two, but since it should be paired with two, we need another right parenthesis.
      • We increment ans to insert one ')' character and decrement x.
      • State after this step: ans = 1, x = 1
    • Index i = 3, character s[i] = ')':
      • This right parenthesis forms a valid pair with the previous '('.
      • We decrement x.
      • State after this step: ans = 1, x = 0
    • Index i = 4, character s[i] = ')':
      • Since x is zero, this right parenthesis is extra and lacks a corresponding '('.
      • We increment ans to add an opening '(' before it.
      • State after this step: ans = 2, x = 0
    • Index i = 5, character s[i] = '(':
      • We have an opening parenthesis that needs two closing ones.
      • Increment x.
      • State after this step: ans = 2, x = 1
  3. Handle unmatched opening parentheses:

    • The iteration ends with x greater than zero; hence, we need to insert two ')' for the unmatched '('.
    • Update ans by x << 1 which is equivalent to adding two ')' characters for the last '('.
    • ans = ans + (x * 2) = 2 + (1 * 2) = 4
  4. Returning the result:

    • With ans equalling to 4, we conclude that four insertions are needed to make the string "(()))(" balanced according to the given rules.

The final balanced string after insertions would look like "(())())(())".

Python Solution

1class Solution:
2    def min_insertions(self, s: str) -> int:
3        # 'balance' keeps track of the balance of the parentheses
4        # 'insertions_needed' will be the answer, representing the minimum insertions needed
5        insertions_needed = balance = 0
6        i, n = 0, len(s)  # 'i' is the current position, 'n' is the length of the string
7
8        while i < n:  # Iterate through the string
9            if s[i] == '(':  # If the current character is an opening parenthesis
10                balance += 1  # Increase balance
11            else:  # If the current character is a closing parenthesis
12                # Check if there's a consecutive closing parenthesis
13                if i < n - 1 and s[i + 1] == ')':
14                    i += 1  # Move to the next character as we've found a pair "))"
15                else:
16                    # If a pair wasn't found, one insertion is needed
17                    insertions_needed += 1
18                # If there is no unmatched opening parenthesis
19                if balance == 0:
20                    # We need an insertion for an opening parenthesis
21                    insertions_needed += 1
22                else:
23                    # Otherwise, use one unmatched opening to balance a pair "))"
24                    balance -= 1
25            i += 1  # Move to the next character
26      
27        # After processing the entire string, we might have unmatched opening parentheses
28        # Each of these needs two insertions to be balanced (one opening parenthesis needs "))")
29        insertions_needed += balance * 2
30      
31        return insertions_needed  # Return the total number of insertions needed
32

Java Solution

1public class Solution {
2  public int minInsertions(String s) {
3    // Initialize a counter for the insertions needed and a counter for open parentheses
4    int insertionsCount = 0, openParensCount = 0;
5    int n = s.length();
6
7    // Iterate through each character in the string
8    for (int i = 0; i < n; ++i) {
9      char currentChar = s.charAt(i);
10
11      // If we encounter an open parenthesis, we increment the open parentheses count
12      if (currentChar == '(') {
13        ++openParensCount;
14      } else {
15        // Check if the next character is also a close parenthesis
16        if (i < n - 1 && s.charAt(i + 1) == ')') {
17          // If it is, we move the index ahead since this is a valid pair of close parentheses
18          ++i;
19        } else {
20          // If it's not, we need an extra insertion to complete a pair
21          ++insertionsCount;
22        }
23
24        // If there are no open parentheses to match, we need an insertion for an open parenthesis
25        if (openParensCount == 0) {
26          ++insertionsCount;
27        } else {
28          // Otherwise, we found a matching pair, so decrement the open parentheses count
29          --openParensCount;
30        }
31      }
32    }
33
34    // After processing all characters, we may have unmatched open parentheses.
35    // Each one requires two insertions to form a complete "()()"
36    insertionsCount += openParensCount << 1;
37
38    // Return the total number of insertions needed to balance the string
39    return insertionsCount;
40  }
41}
42

C++ Solution

1class Solution {
2public:
3    int minInsertions(string s) {
4        int additionalInsertionsNeeded = 0; // This will count the insertions needed to balance the string.
5        int openBracketsCount = 0; // This will keep track of the count of '(' characters seen.
6        int stringLength = s.size(); // Length of the input string.
7
8        for (int i = 0; i < stringLength; ++i) {
9            if (s[i] == '(') {
10                // If the current character is '(', increment the open brackets count.
11                ++openBracketsCount;
12            } else {
13                // If the current character is ')', check if the next character is also ')'.
14                if (i < stringLength - 1 && s[i + 1] == ')') {
15                    // If yes, skip the next character as '))' is a valid pair.
16                    ++i;
17                } else {
18                    // If no, one additional insertion is needed as we expect ')'.
19                    ++additionalInsertionsNeeded;
20                }
21              
22                // Now, we check if there is an open bracket ('(') available to match the closing bracket.
23                if (openBracketsCount == 0) {
24                    // If not, we need to insert an additional '(' before the current ')'.
25                    ++additionalInsertionsNeeded;
26                } else {
27                    // If there is an open bracket, pair it with the current closing bracket.
28                    --openBracketsCount;
29                }
30            }
31        }
32
33        // After processing all characters,
34        // we still might have some '(' brackets open which need to be closed.
35        // For each '(', we need to insert '))' to balance.
36        additionalInsertionsNeeded += openBracketsCount * 2; 
37
38        return additionalInsertionsNeeded; // Return the count of insertions needed.
39    }
40};
41

Typescript Solution

1function minInsertions(s: string): number {
2    let additionalInsertionsNeeded = 0; // This will count the insertions needed to balance the string.
3    let openBracketsCount = 0; // This will keep track of the count of '(' characters seen.
4    let stringLength = s.length; // Length of the input string.
5
6    for (let i = 0; i < stringLength; ++i) {
7        if (s[i] === '(') {
8            // If the current character is '(', increment the open brackets count.
9            ++openBracketsCount;
10        } else {
11            // If the current character is ')', check if the next character is also ')'.
12            if (i < stringLength - 1 && s[i + 1] === ')') {
13                // If yes, skip the next character as '))' is a valid pair.
14                ++i;
15            } else {
16                // If no, one additional insertion is needed because we expect ')' to make a pair.
17                ++additionalInsertionsNeeded;
18            }
19          
20            // Now, check if there is an open bracket ('(') available to match the current closing bracket.
21            if (openBracketsCount === 0) {
22                // If not, insert an additional '(' before the current ')' to balance.
23                ++additionalInsertionsNeeded;
24            } else {
25                // If there is an open bracket, pair it with the current closing bracket.
26                --openBracketsCount;
27            }
28        }
29    }
30
31    // After processing all characters,
32    // there might still be some '(' brackets open which need to be closed.
33    // For each '(', we need to insert '))' to balance.
34    additionalInsertionsNeeded += openBracketsCount * 2; 
35
36    return additionalInsertionsNeeded; // Return the total count of insertions needed.
37}
38

Time and Space Complexity

The given Python code aims to find the minimum number of insertions required to balance a string of parentheses.

Time Complexity:

The time complexity of the function is determined by how it iterates through the input string:

  • There's a single loop through the input string, which traverses each character exactly once.
  • Inside the loop, operations are constant-time: arithmetic, if checks, and a single potential increment of the loop variable i.
  • There is no nested looping or function calls that depend on the size of input inside the loop.

Considering the length of the string as n, the total number of steps is proportional to n. Therefore, the time complexity of the code is O(n).

Space Complexity:

The space complexity is determined by the amount of extra space used besides the input itself. In the case of this function:

  • ans, x, i, and n are simple integer variables that occupy constant space.
  • There is no use of any data structures that can grow with the input size.
  • There are no recursive calls that would add to the call stack space.

Since the space used does not depend on the input size and remains constant, the space complexity of the code is O(1).

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫