Minimum Insertions to Balance a Parentheses String

Med

#1420Time: O(N), where N is the length of the string `s`. We iterate through the string only once.Space: O(1) extra space, as we only use a few integer variables to keep track of counts, regardless of the input string size.1 company

Patterns

Greedy

Data structures

String Stack

Companies

J.P. Morgan

Prompt

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 <= 10⁵
s consists of '(' and ')' only.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through the string while maintaining a count of open parentheses that need to be closed. When a right parenthesis ')' is encountered, we look at the next character to decide if we have a '))' pair or a single ')'. Based on this, we update the count of open parentheses and the number of insertions needed.

Algorithm

Initialize insertions = 0 and open_needed = 0.
Iterate through the string s with an index i.
If s[i] is '(':
- Increment open_needed.
If s[i] is ')':
- Check if i+1 is within bounds and s[i+1] is also ')'.
- If yes (we have a ''))' pair):
  - If open_needed > 0, it means this pair can close an existing open parenthesis. Decrement open_needed.
  - If open_needed == 0, this pair is unmatched. We need to insert a '(' before it. Increment insertions.
  - Increment i to skip the next ')'.
- If no (we have a single ')'):
  - This single ')' must be part of a ''))' pair. We need to insert another ')'. Increment insertions.
  - Now that we have a conceptual ''))' pair, we check if it can close an open parenthesis.
  - If open_needed > 0, decrement open_needed.
  - If open_needed == 0, we also need to insert a '('. Increment insertions again.
After the loop, there might be some remaining open_needed. Each requires a ''))' pair for closing.
Add open_needed * 2 to insertions.
Return insertions.

Walkthrough

This approach solves the problem by performing a single pass through the input string. It uses a counter, openNeeded, to keep track of the number of '(' characters that are waiting for a corresponding ''))' closing pair. The core of the logic involves checking for '))' pairs versus single ')' characters and updating the counts accordingly.

When a '(' is found, we simply increment openNeeded. When a ')' is found, we look ahead. If the next character is also a ')', we treat them as a '))' pair. This pair can satisfy one openNeeded requirement. If there are no open parentheses needing to be closed (openNeeded == 0), we must insert a '(', incrementing our insertions count. If we only find a single ')', we know we must insert another ')' to form a '))' pair. After this conceptual insertion, we proceed as if we found a '))' pair.

Finally, after iterating through the entire string, any remaining openNeeded count signifies open parentheses that were never closed. Each of these requires two ')' insertions to form a '))' pair.

1class Solution {2    public int minInsertions(String s) {3        int insertions = 0;4        int openNeeded = 0;5        int i = 0;6        while (i < s.length()) {7            if (s.charAt(i) == '(') {8                openNeeded++;9                i++;10            } else { // s.charAt(i) == ')'11                // Check for a ')' pair12                if (i + 1 < s.length() && s.charAt(i + 1) == ')') {13                    if (openNeeded > 0) {14                        openNeeded--;15                    } else {16                        // This '))' needs a preceding '('17                        insertions++;18                    }19                    i += 2;20                } else {21                    // This is a single ')'22                    // Step 1: We need to insert one ')' to make a pair.23                    insertions++;24                    // Step 2: Now we have a '))' pair. Check if it can close an open '('25                    if (openNeeded > 0) {26                        openNeeded--;27                    } else {28                        // This new '))' also needs a preceding '('29                        insertions++;30                    }31                    i++;32                }33            }34        }35 36        // Any remaining open brackets need two ')' each.37        insertions += openNeeded * 2;38        return insertions;39    }40}

Complexity

Time

O(N), where N is the length of the string `s`. We iterate through the string only once.

Space

O(1) extra space, as we only use a few integer variables to keep track of counts, regardless of the input string size.

Trade-offs

Pros

Correct and efficient, solving the problem in a single pass.
Utilizes constant extra space, making it memory-efficient.

Cons

The logic is slightly more complex due to the need for lookahead and handling two separate cases for right parentheses (')' vs '))').
The code can be less intuitive to follow because of the nested conditional statements and manual index management.

This is a more streamlined single-pass approach. Instead of counting open parentheses, we maintain a "balance" counter, let's call it right_needed, which represents the number of right parentheses ')' we currently need to see to keep the string balanced. This simplifies the logic by elegantly handling all cases in a unified manner without explicit lookahead.

Algorithm

Initialize insertions = 0 and right_needed = 0.
Iterate through each character c of the string s.
If c is '(':
- If right_needed is odd, it implies we have a single, unmatched ')' from before. To fix this, we must insert one ')' to form a ''))' pair. This pair will close a previously opened '('. So, we increment insertions and decrement right_needed.
- The current '(' requires a ''))' pair. So, we add 2 to right_needed.
If c is ')':
- This ')' helps satisfy our requirement. Decrement right_needed.
- If right_needed becomes negative, it means we have an excess ')' without a matching '('. We must insert a '('. This increments insertions. The newly inserted '(' itself requires a ''))' pair. We have the current ')', so we now need one more ')'. This means right_needed should be 1 (effectively, right_needed goes from -1 to 1, which is right_needed += 2).
After the loop, right_needed holds the count of ')' characters that are still required to balance the string.
Add right_needed to insertions.
Return insertions.

Walkthrough

This optimized approach uses a single counter, rightNeeded, to track the balance of the parentheses. This counter represents the number of ')' characters we expect to see to balance the parentheses encountered so far. This method avoids explicit lookahead and simplifies the code.

The logic is as follows:

When we see a '(', we will need two ')' characters in the future, so we increment rightNeeded by 2. However, if rightNeeded was odd before this, it means there was a lone ')' waiting for a partner. We must first insert a ')' to complete that pair (costing 1 insertion), which in turn closes a pending '(' (decrementing rightNeeded by 1).
When we see a ')', it fulfills one of the needed right parentheses, so we decrement rightNeeded. If rightNeeded drops to -1, it means we have an excess ')' without a preceding '('. We must insert a '(' (costing 1 insertion). This new '(' now requires a '))' pair. Since we have the current ')', our rightNeeded becomes 1.
After the loop, any remaining value in rightNeeded represents the number of ')' we must append to the end to close all remaining open parentheses.

1class Solution {2    public int minInsertions(String s) {3        int insertions = 0;4        int rightNeeded = 0; // Tracks the number of ')' needed5 6        for (char c : s.toCharArray()) {7            if (c == '(') {8                // If rightNeeded is odd, it means we have a single ')' that needs a partner.9                // We must insert one ')' to make ')).' This ')),' will close a pending '('.10                if (rightNeeded % 2 != 0) {11                    insertions++; // Insert one ')'12                    rightNeeded--;  // One '(' is now balanced13                }14                // The current '(' needs two ')'15                rightNeeded += 2;16            } else { // c == ')'17                // We encountered a ')', so our need for ')' decreases.18                rightNeeded--;19                // If rightNeeded becomes negative, we have an excess ')'.20                // We need to insert a '(' to match it.21                if (rightNeeded < 0) {22                    insertions++; // Insert one '('23                    // This new '(' also needs a '))'. We have one ')', so we need one more.24                    // So, rightNeeded goes from -1 to 1.25                    rightNeeded += 2; 26                }27            }28        }29 30        // After iterating, rightNeeded is the number of ')' we still need to insert.31        insertions += rightNeeded;32        return insertions;33    }34}

Complexity

Time

O(N), where N is the length of the string `s`. The algorithm involves a single pass over the string.

Space

O(1) extra space. Only a constant number of integer variables are used.

Trade-offs

Pros

Optimal time and space complexity.
The logic is more elegant and concise compared to the lookahead approach.
It handles all cases smoothly within a single loop structure without manual index management.

Cons

The logic behind the right_needed counter, especially the updates for odd values and when it becomes negative, can be subtle and requires careful thought to understand correctly.

Solutions

Solution

1class Solution {2public3  int minInsertions(String s) {4    int ans = 0, x = 0;5    int n = s.length();6    for (int i = 0; i < n; ++i) {7      if (s.charAt(i) == '(') {8        ++x;9      } else {10        if (i < n - 1 && s.charAt(i + 1) == ')') {11          ++i;12        } else {13          ++ans;14        }15        if (x == 0) {16          ++ans;17        } else {18          --x;19        }20      }21    }22    ans += x << 1;23    return ans;24  }25}

1class Solution {2public:3  int minInsertions(string s) {4    int ans = 0, x = 0;5    int n = s.size();6    for (int i = 0; i < n; ++i) {7      if (s[i] == '(') {8        ++x;9      } else {10        if (i < n - 1 && s[i + 1] == ')') {11          ++i;12        } else {13          ++ans;14        }15        if (x == 0) {16          ++ans;17        } else {18          --x;19        }20      }21    }22    ans += x << 1;23    return ans;24  }25};

1class Solution:2    # 待匹配的左括号加 1 x += 1 else : if i < n - 1 and s [ i + 1 ] == ')' : # 有连续两个右括号，i 往后移动 i += 1 else : # 只有一个右括号，插入一个 ans += 1 if x == 0 : # 无待匹配的左括号，插入一个 ans += 1 else : # 待匹配的左括号减 1 x -= 1 i += 1 # 遍历结束，仍有待匹配的左括号，说明右括号不足，插入 x << 1 个 ans += x << 1 return ans3    def minInsertions(self, s: str) -> int: ans = x = 0 i, n = 0, len(s) while i < n: if s[i] == '(':

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem