Minimum Insertions to Balance a Parentheses String

LeetCode 1648 | Difficulty: Medium

Medium

Problem Description

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^5`

- `s` consists of `'('` and `')'` only.

Topics: String, Stack, Greedy

---

Approach

Stack

Use a stack (LIFO) to track elements that need future processing. Process elements when a "trigger" condition is met (e.g., finding a smaller/larger element). Monotonic stack maintains elements in sorted order for next greater/smaller element problems.

When to use

Matching brackets, next greater element, evaluating expressions, backtracking history.

Greedy

At each step, make the locally optimal choice. The challenge is proving the greedy choice leads to a global optimum. Look for: can I sort by some criterion? Does choosing the best option now ever hurt future choices?

When to use

Interval scheduling, activity selection, minimum coins (certain denominations), Huffman coding.

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

---

Solutions

Solution 1: C# (Best: 84 ms)

Metric	Value
Runtime	84 ms
Memory	42.5 MB
Date	2022-01-23

Solution

public class Solution {
    public int MinInsertions(string s) {
        int res = 0, right=0;
    foreach (var c in s)
    {
        if(c=='(') {
         if(right%2 == 1)
         {
            right--;
            res++;
         }
            right += 2;
        }
        else
        {
            right--;
            if(right<0) {
                right += 2;
                res++;
            }
        }
    }
    return res + right;
    }
}

📜 1 more C# submission(s)

Submission (2022-01-23) — 104 ms, 39.7 MB

public class Solution {
    public int MinInsertions(string s) {
        int res = 0, right=0;
    foreach (var c in s)
    {
        if(c=='(') {
         if(right%2 == 1)
         {
            right--;
            res++;
         }
            right += 2;
        }
        else
        {
            right--;
            if(right<0) {
                right += 2;
                res++;
            }
        }
    }
    return res + right;
    }
}

---

Complexity Analysis

Approach	Time	Space
Stack	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Think about what triggers a pop: is it finding a match, or finding a smaller/larger element?
• LeetCode provides 2 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Use a stack to keep opening brackets. If you face single closing ')' add 1 to the answer and consider it as '))'.

Hint 2: If you have '))' with empty stack, add 1 to the answer, If after finishing you have x opening remaining in the stack, add 2x to the answer.