Minimum Add to Make Parentheses Valid - Practice Coding Problems

Minimum Add to Make Parentheses Valid - Problem

A parentheses string is valid if and only if:

It is the empty string
It can be written as AB (A concatenated with B), where A and B are valid strings
It can be written as (A), where A is a valid string

You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string.

For example, if s = "())", you can insert an opening parenthesis to be "(())" or a closing parenthesis to be "())".

Return the minimum number of moves required to make s valid.

Input & Output

Example 1 — Unmatched Closing

$ Input: s = "())"

› Output: 1

💡 Note: We have one '(' and two ')'. The first ')' matches with '(', but the second ')' is unmatched. We need to add one '(' at the beginning to make it valid: "(())".

Example 2 — Unmatched Opening

$ Input: s = "((("

› Output: 3

💡 Note: We have three unmatched '(' characters. We need to add three ')' characters to make it valid: "((()))".

Example 3 — Empty String

$ Input: s = ""

› Output: 0

💡 Note: Empty string is already valid, no additions needed.

Constraints

1 ≤ s.length ≤ 1000
s[i] is either '(' or ')'

Visualization

Tap to expand

Understanding the Visualization

Input

Invalid parentheses string with mismatched pairs

Process

Count unmatched opening and closing parentheses

Output

Minimum additions needed to make string valid

Key Takeaway

🎯 Key Insight: Count unmatched parentheses by tracking balance - negative balance means unmatched closing, positive balance means unmatched opening

Asked in

F Facebook 25 G Google 20 a Amazon 15

The key insight is to track unmatched opening and closing parentheses separately. Best approach uses single-pass greedy counting. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Insertions	O(2^n)	O(n)	Try inserting parentheses at every position until string becomes valid
Stack Simulation	O(n)	O(1)	Use stack-like counting to track unmatched parentheses
Greedy Balance Tracking	O(n)	O(1)	Track balance and count minimum additions greedily

Brute Force - Try All Insertions — Algorithm Steps

Generate all possible insertion positions
For each combination, insert parentheses
Check if resulting string is valid
Return minimum insertions needed

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial String

Start with invalid parentheses string

Try Insertions

Generate all possible insertion combinations

Find Minimum

Return the minimum valid insertions

Code -

solution.c — C

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

int isValid(const char* s) {
    int balance = 0;
    for (int i = 0; s[i]; i++) {
        if (s[i] == '(') {
            balance++;
        } else if (s[i] == ')') {
            balance--;
            if (balance < 0) return 0;
        }
    }
    return balance == 0;
}

int minInsertions(const char* s, int insertions, int maxLen) {
    if (isValid(s)) {
        return insertions;
    }
    
    if (insertions > maxLen) {
        return INT_MAX;
    }
    
    int minMoves = INT_MAX;
    int len = strlen(s);
    
    for (int i = 0; i <= len; i++) {
        char* newStr1 = malloc(len + 2);
        strncpy(newStr1, s, i);
        newStr1[i] = '(';
        strcpy(newStr1 + i + 1, s + i);
        
        int result1 = minInsertions(newStr1, insertions + 1, maxLen);
        if (result1 < minMoves) minMoves = result1;
        
        char* newStr2 = malloc(len + 2);
        strncpy(newStr2, s, i);
        newStr2[i] = ')';
        strcpy(newStr2 + i + 1, s + i);
        
        int result2 = minInsertions(newStr2, insertions + 1, maxLen);
        if (result2 < minMoves) minMoves = result2;
        
        free(newStr1);
        free(newStr2);
    }
    
    return minMoves;
}

int solution(const char* s) {
    return minInsertions(s, 0, strlen(s));
}

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

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

For each position we can insert 0, 1, or more parentheses, leading to exponential combinations

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth and string storage for combinations

⚡ Linearithmic Space

125.0K Views

Medium Frequency

~15 min Avg. Time

2.2K 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

Brute Force - Try All Insertions — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler