LeetCode 1541 - Minimum Insertions to Balance a Parentheses String

Difficulty: 🟡 Medium
Topics: String, Stack, Greedy

Solution

Problem Understanding

This problem asks us to transform a string of parentheses into a special kind of balanced parentheses string using the minimum number of insertions.

Unlike the standard parentheses balancing problem, this problem defines balance differently. Every opening parenthesis '(' must be matched with exactly two consecutive closing parentheses '))'.

That means:

One '(' requires two ')'
The two closing parentheses must appear consecutively
The opening parenthesis must appear before its matching '))'

For example:

"())" is balanced because '(' is matched with '))'
"(())))" is balanced because both '(' characters are properly matched
"(()))" is not balanced because the first '(' only has one ')' paired with it

The input is a string s containing only '(' and ')'. We are allowed to insert additional parentheses anywhere in the string. The goal is to compute the minimum number of insertions required to make the string balanced according to the special rules above.

The constraints are important:

1 <= s.length <= 10^5
Only '(' and ')' appear

Since the input size can be as large as one hundred thousand characters, any algorithm worse than linear time will likely be too slow. This immediately rules out expensive recursive or brute force search solutions.

Several edge cases are especially important:

Strings that start with ')'
Strings with odd numbers of consecutive ')'
Strings ending with unmatched '('
Strings where ')' characters do not appear in pairs
Completely unbalanced strings like "))))" or "(((("

A naive implementation can easily mishandle situations where a single ')' appears instead of a required '))'.

Approaches

Brute Force Approach

A brute force solution would attempt to generate all possible valid insertion combinations and check whether the resulting string becomes balanced.

One possible strategy is:

At every position, try inserting '(' or ')'
Recursively continue building modified strings
Validate whether the final string satisfies the balance rules
Track the minimum insertions among all valid constructions

This works because it eventually explores every possible insertion arrangement, guaranteeing that the optimal answer is found.

However, this approach is completely impractical. The number of possible insertion combinations grows exponentially with the string length. Even small inputs would generate an enormous search space.

Additionally, validating balance repeatedly adds further overhead.

With input sizes up to 10^5, brute force is impossible.

Optimal Greedy Approach

The key insight is that we do not actually need to construct the final balanced string. We only need to count how many insertions are necessary.

We can process the string from left to right while tracking:

How many closing parentheses are still needed
How many insertions have already been made

Each '(' requires exactly two ')', so every time we encounter '(', we increase the number of needed closing parentheses by 2.

When we encounter ')', we decrease the required closing count by 1.

The tricky part is that closing parentheses must come in pairs. If we ever need an odd number of closing parentheses, that means a single ')' is missing its partner. In that situation, we insert one ')' immediately.

Similarly, if we encounter a ')' when no opening parenthesis is available, we must insert a '('.

This greedy strategy works because every correction is made at the earliest possible moment, preventing future inconsistencies from growing larger.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Tries all insertion possibilities
Optimal Greedy	O(n)	O(1)	Tracks required closing parentheses while scanning

Algorithm Walkthrough

Initialize two variables:

insertions, which counts how many characters we insert
needed, which tracks how many closing parentheses are still required

Traverse the string character by character from left to right.
If the current character is '(':

This opening parenthesis requires two closing parentheses
Increase needed by 2

After increasing needed, check whether needed is odd.

A balanced structure requires closing parentheses to appear in pairs
If needed becomes odd, that means one unmatched ')' already exists
Insert one ')'
Increment insertions
Decrease needed by 1

If the current character is ')':

Decrease needed by 1 because one required closing parenthesis has been provided

If needed becomes negative:

This means we encountered a closing parenthesis without a matching opening parenthesis
Insert one '('
Increment insertions
Set needed to 1
We set it to 1 because the inserted '(' requires two ')', and one of them has already been consumed by the current character

Continue processing until the entire string has been scanned.
After traversal finishes:

Some opening parentheses may still be unmatched
The variable needed tells us exactly how many ')' must still be inserted
Return insertions + needed

Why it works

The algorithm maintains an invariant that needed always represents the exact number of closing parentheses still required to complete a valid balanced structure.

Whenever the structure becomes invalid:

An odd needed value indicates an incomplete '))' pair
A negative needed value indicates a missing '('

The algorithm immediately fixes each violation with the minimum possible insertion. Since every correction is locally optimal and unavoidable, the total number of insertions is globally minimal.

Python Solution

class Solution:
    def minInsertions(self, s: str) -> int:
        insertions = 0
        needed = 0

        for char in s:
            if char == '(':
                needed += 2

                if needed % 2 == 1:
                    insertions += 1
                    needed -= 1
            else:
                needed -= 1

                if needed < 0:
                    insertions += 1
                    needed = 1

        return insertions + needed

The implementation directly follows the greedy algorithm described earlier.

The variable insertions stores the number of characters we artificially add during processing.

The variable needed tracks how many closing parentheses are still required.

When encountering '(', we increase needed by 2 because every opening parenthesis requires exactly two closing parentheses.

If needed becomes odd after adding two, that means there is currently a dangling single ')' somewhere. We immediately insert one additional ')' to complete the pair.

When processing ')', we reduce needed because one required closing parenthesis has now appeared.

If needed becomes negative, there was no matching '('. We insert one '(' and reset needed to 1.

Finally, after processing the whole string, any remaining needed value represents unmatched required closing parentheses, so we add that directly to the answer.

Go Solution

func minInsertions(s string) int {
    insertions := 0
    needed := 0

    for _, char := range s {
        if char == '(' {
            needed += 2

            if needed%2 == 1 {
                insertions++
                needed--
            }
        } else {
            needed--

            if needed < 0 {
                insertions++
                needed = 1
            }
        }
    }

    return insertions + needed
}

The Go implementation mirrors the Python logic almost exactly.

One difference is that Go iterates over characters using range, which produces rune values. Since the input contains only ASCII parentheses, direct comparisons with '(' and ')' work correctly.

No special overflow handling is necessary because the maximum number of insertions is proportional to the input length, which easily fits within Go's integer range.

Worked Examples

Example 1

Input: s = "(()))"

Step	Character	needed Before	Action	needed After
1	`(`	0	Add 2 needed	2
2	`(`	2	Add 2 needed	4
3	`)`	4	Consume one `)`	3
4	`)`	3	Consume one `)`	2
5	`)`	2	Consume one `)`	1

Traversal ends with:

needed = 1
insertions = 0

Final answer:

0 + 1 = 1

Example 2

Input: s = "())"

Step	Character	needed Before	Action	needed After
1	`(`	0	Add 2 needed	2
2	`)`	2	Consume one `)`	1
3	`)`	1	Consume one `)`	0

Traversal finishes with everything balanced.

Final answer:

Example 3

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

Step	Character	needed Before	Action	needed After	insertions
1	`)`	0	Missing `'('`, insert one	1	1
2	`)`	1	Consume one `)`	0	1
3	`(`	0	Add 2 needed	2	1
4	`)`	2	Consume one `)`	1	1
5	`)`	1	Consume one `)`	0	1
6	`(`	0	Add 2 needed	2	1

Traversal ends with:

needed = 2
insertions = 1

Final answer:

1 + 2 = 3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed exactly once
Space	O(1)	Only a few integer variables are used

The algorithm performs a single left to right traversal of the input string. Every operation inside the loop takes constant time, so the total running time grows linearly with the input size.

No auxiliary data structures are required. The algorithm only maintains two integer counters, giving constant extra space usage.

Test Cases

solution = Solution()

assert solution.minInsertions("(()))") == 1  # Missing one closing parenthesis
assert solution.minInsertions("())") == 0  # Already balanced
assert solution.minInsertions("))())(") == 3  # Needs opening and closing insertions

assert solution.minInsertions("(") == 2  # Single opening parenthesis
assert solution.minInsertions(")") == 2  # Single closing parenthesis
assert solution.minInsertions("))") == 1  # Need one opening parenthesis

assert solution.minInsertions("(((") == 6  # Every opening needs two closings
assert solution.minInsertions(")))") == 3  # Multiple unmatched closings

assert solution.minInsertions("()") == 1  # One more closing needed
assert solution.minInsertions("())(") == 2  # Balanced prefix plus unmatched opening

assert solution.minInsertions("") == 0  # Empty string edge case
assert solution.minInsertions("(())))") == 0  # Already balanced complex case
assert solution.minInsertions("(()))(()))()())))") == 4  # Larger mixed case

Test	Why
`"(()))"`	Tests missing single closing parenthesis
`"())"`	Tests already balanced input
`"))())("`	Tests unmatched closings and trailing opening
`"("`	Tests lone opening parenthesis
`")"`	Tests lone closing parenthesis
`"))"`	Tests unmatched closing pair
`"((("`	Tests many unmatched openings
`")))"`	Tests many unmatched closings
`"()"`	Tests incomplete closing pair
`"())("`	Tests mixed imbalance
`""`	Tests empty input
`"(())))"`	Tests valid longer balanced string
`"(()))(()))()())))"`	Tests larger mixed configuration

Edge Cases

One important edge case occurs when the string starts with ')'. Since every closing sequence must correspond to a previous '(', a leading ')' is immediately invalid. A buggy implementation might incorrectly decrement counters into negative values without fixing the structure. This implementation detects needed < 0 and inserts a matching '(' immediately.

Another tricky case happens when a single ')' appears without its partner. Since every closing must be part of a consecutive '))', odd counts of required closing parentheses indicate an incomplete pair. The implementation handles this by checking whether needed becomes odd after processing '(', then inserting one ')' immediately.

A final important edge case is trailing unmatched '('. For example, "(((" requires six closing parentheses. Some implementations incorrectly assume balance at the end of traversal. This solution correctly preserves the remaining required count in needed and adds it to the final answer.

A subtle edge case is the empty string. Although the official constraints start from length 1, robust implementations should still handle empty input correctly. Since the loop never executes, both counters remain zero and the method correctly returns 0.