Minimum Insertions to Balance a Parentheses String

Minimum Insertions to Balance a Parentheses String - Problem

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.

Input & Output

Example 1 — Basic Unbalanced

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

› Output: 1

💡 Note: We have "(()))" which has one '(' needing two ')', but there are three ')'. The second and third ')' form a valid pair ')', but the last ')' is unmatched. We need to insert one ')' to make it "(()))".

Example 2 — Multiple Opens

$ Input: s = "((("

› Output: 6

💡 Note: We have 3 opening parentheses, each needing 2 closing parentheses. So we need 3 × 2 = 6 insertions: "(((" → "((())))".

Example 3 — Mixed Case

$ Input: s = "())("

› Output: 2

💡 Note: "())" is balanced (one '(' with ')'), but we have an extra ')' and an unmatched '(' at the end. Need to insert one '(' for the extra ')' and two ')' for the final '('.

Constraints

1 ≤ s.length ≤ 10⁵
s consists of only '(' and ')'

Visualization

Tap to expand

Understanding the Visualization

Input String

String with '(' and ')' characters

Balance Rule

Each '(' requires exactly 2 ')' characters

Minimum Insertions

Count needed characters to achieve balance

Key Takeaway

🎯 Key Insight: Each '(' needs exactly 2 ')' characters - track the balance deficit greedily

Asked in

F Facebook 45 G Google 38 M Microsoft 32 a Amazon 28

The key insight is that each '(' needs exactly two ')' characters to balance. The optimal approach uses a greedy strategy tracking the running deficit of needed closing parentheses. Best approach: Greedy Balance Tracking - Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Stack-Based Tracking	O(n)	O(1)	Use stack to track unmatched opens and process closes greedily
Greedy Balance Tracking	O(n)	O(1)	Track balance deficit and required insertions in single pass
Recursive Try All Insertions	O(3ⁿ)	O(n)	Try inserting parentheses at every position until balanced

Stack-Based Tracking — Algorithm Steps

Initialize counter for unmatched opens and result for insertions
For each '(': increment open counter
For each ')': try to pair with next ')' or previous '('
Add remaining unmatched opens * 2 to result

Visualization

Tap to expand

Step-by-Step Walkthrough

Track Opens

Count unmatched '(' characters

Process Closes

Handle single ')' and pairs '))'

Final Count

Add insertions for remaining opens

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

int solution(const char* s) {
    int opens = 0;
    int insertions = 0;
    int len = strlen(s);
    
    int i = 0;
    while (i < len) {
        if (s[i] == '(') {
            opens++;
        } else {
            if (i + 1 < len && s[i + 1] == ')') {
                if (opens > 0) {
                    opens--;
                } else {
                    insertions++;
                }
                i++;
            } else {
                if (opens > 0) {
                    opens--;
                    insertions++;
                } else {
                    insertions += 2;
                }
            }
        }
        i++;
    }
    
    insertions += opens * 2;
    
    return insertions;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    printf("%d\n", solution(s));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the string

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

87.5K Views

Medium Frequency

~15 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Stack-Based Tracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler