#1541

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Minimum Insertions to Balance a Parentheses String

Compute the minimum insertions to transform a parentheses string into a balanced string using efficient stack tracking.

Problem Statement

You are given a string s containing only '(' and ')'. A string is balanced if each '(' is matched with exactly two consecutive ')', and each ')' properly closes an opening parenthesis. You can insert '(' or ')' at any position to achieve balance.

Determine the minimum number of insertions needed to make s balanced. For example, s = "(()))" requires one extra ')' at the end, while s = "))())(" requires three insertions to match all parentheses according to the double-close rule.

Examples

Example 1

Input: s = "(()))"

Output: 1

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

The string is already balanced.

Example 3

Input: s = "))())("

Output: 3

Add '(' to match the first '))', Add '))' to match the last '('.

Constraints

1 <= s.length <= 105
s consists of '(' and ')' only.

Solution Approach

Stack-Based Tracking

Use a stack to record each '(' encountered. When ')' appears, check if the top of the stack can be matched. If a single ')' appears without a matching '(', increment the insertion counter and treat it as '))'.

Greedy Handling of Single Closings

Whenever a lone ')' occurs, add one insertion immediately to simulate the second ')' needed. This prevents cascading mismatches and ensures the stack accurately reflects unmatched '(' at any step.

Finalize Remaining Openings

After traversing the string, any remaining '(' in the stack require two ')' insertions each to balance according to the 'double close' rule. Sum these with prior insertions for the total minimum required.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each character is processed once, and stack operations are O(1). Space complexity is O(n) in the worst case to store all '(' in the stack.

What Interviewers Usually Probe

Expect clarity in handling unmatched ')' with the double-close requirement.
Watch for correct greedy insertions rather than global balancing attempts.
Check understanding of stack usage to maintain state efficiently.

Common Pitfalls or Variants

Common pitfalls

Forgetting that each '(' requires exactly two ')' for a match, not one.
Not treating a lone ')' as needing an extra insertion immediately.
Attempting to rebalance from the end instead of processing left to right.

Follow-up variants

Input strings with only '(' or only ')' to test extreme insertions.
Strings with nested patterns like '((()))))' to verify stack handling.
Alternating parentheses such as '())(()))(' to stress greedy insertion logic.

FAQ

What is the key pattern in Minimum Insertions to Balance a Parentheses String?

The core pattern is stack-based state management, tracking '(' and handling lone ')' greedily for exact minimum insertions.

How do I handle a single ')' in this problem?

Treat a single ')' as needing an extra ')' insertion immediately to satisfy the double-close requirement.

Why is a stack necessary for this problem?

A stack efficiently records unmatched '(' and helps decide when insertions are needed for subsequent ')' characters.

Can this be solved without extra space?

Yes, by tracking the number of needed ')' and unmatched '(', but explicit stack usage makes logic clearer and avoids errors.

What is the time complexity of the optimal solution?

It is O(n) because each character is visited once and stack operations are O(1), providing linear performance.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

class Solution:
    def minInsertions(self, s: str) -> int:
        ans = x = 0
        i, n = 0, len(s)
        while i < n:
            if s[i] == '(':
                # 待匹配的左括号加 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 ans

Continue Practicing

#1717 maximum score from removing substrings #1963 minimum number of swaps to make the string balanced #1081 smallest subsequence of distinct characters