Remove Invalid Parentheses - Practice Coding Problems

Remove Invalid Parentheses - Problem

Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.

Return a list of unique strings that are valid with the minimum number of removals. You may return the answer in any order.

A valid string has properly matched parentheses where:

Every opening parenthesis ( has a corresponding closing parenthesis )
The closing parentheses appear after their corresponding opening parentheses

Input & Output

Example 1 — Extra Closing Parenthesis

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

› Output: ["()()", "(())"]

💡 Note: Remove one ')' to get valid strings. Two possibilities: remove the 4th character to get "()()" or remove the 5th character to get "(())"

Example 2 — Multiple Invalid Parentheses

$ Input: s = "((("

› Output: [""]

💡 Note: All three opening parentheses are invalid since there are no closing ones. Remove all parentheses to get empty string.

Example 3 — Already Valid

$ Input: s = "()"

› Output: ["()"]

💡 Note: String is already valid, no removals needed. Return the original string.

Constraints

1 ≤ s.length ≤ 25
s consists of lowercase English letters and parentheses '(' and ')'
There will be at most 20 parentheses in s

Visualization

Tap to expand

Understanding the Visualization

Input

String with invalid parentheses: ()())

Process

Find all ways to remove minimum parentheses

Output

All valid strings with minimum removals

Key Takeaway

🎯 Key Insight: BFS naturally finds minimum removals first, while backtracking with pre-calculated limits provides efficient pruning

Asked in

f Facebook 85 G Google 65 a Amazon 45 M Microsoft 35

The key insight is to use BFS to naturally find solutions with minimum removals first, or backtracking with pre-calculated removal counts for efficient pruning. Best approach is BFS for simplicity or backtracking for memory efficiency. Time: O(2^n), Space: O(2^n) for BFS, O(n) for backtracking.

Common Approaches

Approach	Time	Space	Notes
✓ BFS - Level by Level Removal	O(2^n)	O(2^n)	Use BFS to explore strings level by level, finding minimum removals first
Backtracking with Pruning	O(2^n)	O(n)	Use DFS with smart pruning to avoid unnecessary explorations
Brute Force - Try All Combinations	O(2^n)	O(2^n)	Generate all possible substrings and check which ones are valid

BFS - Level by Level Removal — Algorithm Steps

Start BFS with original string
For each level, try removing each parenthesis
Stop when first valid strings are found
Return all valid strings at that level

Visualization

Tap to expand

Step-by-Step Walkthrough

Level 0

Start with original string

Level 1

Remove one parenthesis at a time

Found

Stop when valid strings found

Code -

solution.c — C

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

#define MAX_QUEUE 10000
#define MAX_LEN 1000

bool isValid(const char* str) {
    int count = 0;
    for (int i = 0; str[i]; i++) {
        if (str[i] == '(') {
            count++;
        } else if (str[i] == ')') {
            count--;
            if (count < 0) return false;
        }
    }
    return count == 0;
}

char** solution(char* s, int* returnSize) {
    char queue[MAX_QUEUE][MAX_LEN];
    bool visited[MAX_QUEUE] = {false};
    int front = 0, rear = 0;
    char** results = (char**)malloc(1000 * sizeof(char*));
    int count = 0;
    
    strcpy(queue[rear++], s);
    bool found = false;
    
    while (front < rear && !found) {
        int levelSize = rear - front;
        
        for (int i = 0; i < levelSize && !found; i++) {
            char* current = queue[front++];
            
            if (isValid(current)) {
                results[count] = (char*)malloc((strlen(current) + 1) * sizeof(char));
                strcpy(results[count], current);
                count++;
                found = true;
            }
            
            if (!found) {
                // Try removing each parenthesis
                for (int j = 0; current[j]; j++) {
                    if (current[j] == '(' || current[j] == ')') {
                        char nextString[MAX_LEN];
                        strncpy(nextString, current, j);
                        strcpy(nextString + j, current + j + 1);
                        
                        // Simple duplicate check
                        bool isDuplicate = false;
                        for (int k = front; k < rear; k++) {
                            if (strcmp(queue[k], nextString) == 0) {
                                isDuplicate = true;
                                break;
                            }
                        }
                        
                        if (!isDuplicate && rear < MAX_QUEUE) {
                            strcpy(queue[rear++], nextString);
                        }
                    }
                }
            }
        }
    }
    
    *returnSize = count;
    if (count == 0) {
        results[0] = (char*)malloc(2 * sizeof(char));
        strcpy(results[0], "");
        *returnSize = 1;
    }
    return results;
}

int main() {
    char s[1000];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    int returnSize;
    char** result = solution(s, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("\"%s\"", result[i]);
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

In worst case, we still explore exponential combinations, but BFS pruning helps significantly

⚠ Quadratic Growth

Space Complexity

O(2^n)

BFS queue can contain exponential number of strings at each level

⚠ Quadratic Space

125.0K Views

High Frequency

~35 min Avg. Time

3.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

BFS - Level by Level Removal — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler