Problem Description

Given a string s consisting only of the characters '(' and ')', your task is to determine the minimum number of insertions needed to make s a balanced parentheses string.

A parentheses string is considered balanced if:

• Every opening bracket '(' has a corresponding closing bracket ')'.
• Brackets are closed in the correct order (i.e., you never close before opening).

For example, for s = "())", the answer is 1 because you can insert one '(' at the start or one ')' at the end to balance it.

Constraints:

• 1 <= s.length <= 10^5
• s only contains '(' and ')'

Thought Process

At first glance, one might consider generating all possible insertions to balance the string, but this is highly inefficient. Instead, let's think about what it means for a string to be unbalanced:

• If we have more closing brackets ')' than opening brackets '(' at any point, we need to insert an opening bracket.
• If we finish parsing the string and have more opening brackets than closing brackets, we need to insert closing brackets.

This approach avoids unnecessary work by only counting the minimal insertions needed as we walk through the string once.

Solution Approach

Let's break down the solution step by step:

1. Initialize two counters:
   • res: Number of insertions needed (starts at 0).
   • balance: Tracks the current balance of parentheses (starts at 0).
2. Iterate over each character in the string s:
   • If the character is '(', increment balance (we need one more ')' in the future).
   • If the character is ')', decrement balance (we close one open parenthesis).
3. Handle negative balance:
   • If balance becomes negative, it means we have an unmatched ')'.
   • Increment res (insert an opening bracket), and reset balance to 0.
4. After the loop:
   • If balance > 0, it means we have unmatched '(' left, so we need to insert balance closing brackets.
   • Return res + balance as the final answer.

This approach is efficient because it scans the string once and uses constant extra space.

Example Walkthrough

Let's consider the input s = "())(".

• Start with res = 0, balance = 0.
• Character 1: '(' → balance = 1
• Character 2: ')' → balance = 0
• Character 3: ')' → balance = -1
  • Since balance < 0, increment res to 1 and reset balance = 0.
• Character 4: '(' → balance = 1

End of string: balance = 1 (one unmatched '('), so we need one more ')'.

Final answer: res + balance = 1 + 1 = 2.

Time and Space Complexity

Brute-force approach:

• Would involve generating all possible insertions and checking validity, which is exponential in time and space.

• Time Complexity: O(n), where n is the length of s, since we scan the string once.
• Space Complexity: O(1), since we only use two integer variables regardless of input size.

Code Implementation

class Solution:
    def minInsertions(self, s: str) -> int:
        res = 0
        balance = 0
        for c in s:
            if c == '(':
                balance += 1
            else:  # c == ')'
                balance -= 1
                if balance < 0:
                    res += 1
                    balance = 0
        return res + balance
      

class Solution {
public:
    int minInsertions(string s) {
        int res = 0, balance = 0;
        for (char c : s) {
            if (c == '(') {
                balance++;
            } else {
                balance--;
                if (balance < 0) {
                    res++;
                    balance = 0;
                }
            }
        }
        return res + balance;
    }
};
      

class Solution {
    public int minInsertions(String s) {
        int res = 0, balance = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                balance++;
            } else {
                balance--;
                if (balance < 0) {
                    res++;
                    balance = 0;
                }
            }
        }
        return res + balance;
    }
}
      

var minInsertions = function(s) {
    let res = 0, balance = 0;
    for (const c of s) {
        if (c === '(') {
            balance++;
        } else {
            balance--;
            if (balance < 0) {
                res++;
                balance = 0;
            }
        }
    }
    return res + balance;
};
      

Summary

The core insight is to track the balance of open and close parentheses as we scan the string. Every time we see an unmatched closing parenthesis, we count an insertion. Any unmatched opening parentheses at the end also require insertions. This leads to an efficient O(n) time, O(1) space solution that avoids brute-force and leverages simple counting for elegance and clarity.