Minimum Insertions to Balance a Parentheses String: Greedy Counter Pattern

Given a parentheses string s containing only "(" and ")", a balanced string is defined with a twist: every "(" must be matched by exactly two consecutive ")" characters. Return the minimum number of insertions (of either "(" or ")") needed to make s balanced.

This is LeetCode 1541: Minimum Insertions to Balance a Parentheses String, a medium problem that builds on the classic parentheses matching idea but changes the rules enough that the standard one-counter approach needs a careful update. Instead of each "(" needing one ")", it needs two, which creates new edge cases you have to handle during a single pass.

Why this problem matters

Classic parentheses balancing (like Valid Parentheses) uses a single counter or a stack. Increment for "(", decrement for ")", and check that the counter never goes negative. That pattern is so common it becomes automatic.

This problem forces you to rethink that automatic approach. The "each open needs two closes" rule means you cannot just decrement by one when you see ")". You have to look ahead for a second ")", and when it is missing, you need to decide whether to insert the missing ")" and consume the pair, or handle a lone ")" differently. It teaches you how to adapt a well-known greedy template to a slightly different constraint, which is exactly the kind of thinking interviews test.

The key insight

Track two counters: open for unmatched "(" characters, and insertions for characters you need to insert.

When you see "(", increment open. That open paren now needs two closing parens.

When you see ")", check whether the next character is also ")". If yes, you have a complete "))" pair. If open > 0, consume it by decrementing open. If open == 0, you need to insert a "(", so increment insertions.

If there is no second ")" following, you need to insert one ")" to form the pair. That costs one insertion. Then apply the same matching logic: if open > 0, decrement it. If open == 0, also insert a "(" (another insertion).

At the end, any remaining open count means unmatched "(" characters, each needing two ")" inserted. Add open * 2 to your insertions.

The solution

def min_insertions(s):
    open_count = 0
    insertions = 0
    i = 0

    while i < len(s):
        if s[i] == "(":
            open_count += 1
            i += 1
        else:
            if i + 1 < len(s) and s[i + 1] == ")":
                i += 2
            else:
                insertions += 1
                i += 1

            if open_count > 0:
                open_count -= 1
            else:
                insertions += 1

    insertions += open_count * 2
    return insertions

The loop uses a while with manual index advancement instead of a for loop, because when you find a "))" pair you need to skip two characters at once.

Here is how each branch works:

1. See "(": increment open_count and advance by 1.
2. See ")": check if the next character is also ")". If yes, you have a natural "))" pair, so advance by 2. If no, you need to insert one ")", so add 1 to insertions and advance by 1.
3. After handling the close pair: try to match it with an open "(". If open_count > 0, decrement it. If open_count == 0, you also need to insert a "(", so add 1 more to insertions.
4. After the loop: each remaining unmatched "(" needs 2 close insertions.

Visual walkthrough

Walking through "(()))":

• Index 0 and 1 are both "(", so open goes to 2.
• Index 2 and 3 form a "))" pair. Match with one open. open drops to 1.
• Index 4 is a lone ")". Insert one ")" to form a pair (insertions = 1). Match with the remaining open. open drops to 0.
• End of string: open = 0, so no extra insertions for unmatched opens.
• Final answer: insertions + open * 2 = 1 + 0 = 1.

Complexity analysis

The algorithm makes a single pass through the string, advancing the index by 1 or 2 at each step. Every character is visited at most once. The only storage is two integer counters, giving constant space.

The building blocks

1. Tracking unmatched opens

if s[i] == "(":
    open_count += 1
    i += 1

This is the same pattern used in every parentheses problem. An open paren is "pending" until it gets matched with closing parens. The counter tells you how many are still waiting. When you see a valid closing group, you decrement. If the counter is zero and you see a closing group, that means you need to insert an opener.

2. Handling the double-close requirement

if i + 1 < len(s) and s[i + 1] == ")":
    i += 2
else:
    insertions += 1
    i += 1

This is the part that differs from standard parentheses matching. Instead of consuming one ")" at a time, you look ahead for a second one. If you find it, consume both and advance by 2. If you do not find it, insert the missing ")" and advance by 1. The look-ahead is what makes the while loop necessary instead of a for loop.

Edge cases

• Empty string: no characters, no insertions needed. Return 0.
• All opens "(((" (length 3): each "(" needs two ")", so you need 6 insertions.
• All closes ")))" (length 3): the first two ")" form a pair, but there is no "(" for them, so insert one "(". The third ")" is alone, so insert one ")" to form a pair plus one "(" to match. Total: 3 insertions.
• Already balanced "(()))" wait, that is 5 chars: trace through carefully. This string actually needs 1 insertion.
• Single character "(" or ")": "(" needs 2 close insertions. ")" needs 1 close insertion and 1 open insertion, totaling 2.
• Alternating "()()()" (standard balanced, but not here): each "(" only has one ")" following it, so each pair needs one extra ")" inserted. For 3 pairs, that is 3 insertions.

From understanding to recall

You have seen the greedy solution and traced through the logic. The key is the look-ahead for the second ")", the manual index advancement, and the final open * 2 cleanup. These are small details, but getting any of them wrong in an interview means a wrong answer.

Spaced repetition turns understanding into automatic recall. You practice writing this solution from scratch at increasing intervals. After a few rounds, you see "each open needs k closes" and the greedy structure flows out without hesitation. The look-ahead, the insertion counting, and the cleanup step are all burned into muscle memory.

Related posts

• Valid Parentheses - The foundational parentheses matching problem using a stack
• Generate Parentheses - Building valid parentheses strings with backtracking
• Longest Valid Parentheses - Finding the longest balanced substring

CodeBricks breaks LeetCode 1541 into its greedy counting and parentheses matching building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a parentheses variation shows up in your interview, you adapt the template without hesitation.