Remove Invalid Parentheses

📋

Problem

Imagine you receive a corrupted string of parentheses from a user input or a legacy system, and you need to clean it up by removing the minimum number of invalid parentheses to make it valid again.

Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid. Return all possible results in any order. A string is valid if parentheses are balanced and properly closed.

1 ≤ s.length ≤ 10^5s consists of lowercase English letters and parentheses '(' and ')'.

Edge cases: Empty string → returns [""]String with no parentheses → returns the string itselfString with all valid parentheses → returns the string itself

</>

IDE

def remove_invalid_parentheses(s: str) -> list:public List<String> removeInvalidParentheses(String s)vector<string> removeInvalidParentheses(string s)function removeInvalidParentheses(s)

def remove_invalid_parentheses(s: str) -> list:
    # Write your solution here
    pass

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
#include <string>
using namespace std;

vector<string> removeInvalidParentheses(string s) {
    // Write your solution here
    return {};
}

function removeInvalidParentheses(s) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: ()())()Returned input string without removing invalid parentheses; failed to find minimal removals.✅ Implement BFS or backtracking to remove invalid parentheses and check validity at each step.

Wrong: ()()()Returned only one valid string due to greedy removal of first invalid parenthesis.✅ Use BFS level-by-level to find all minimal removals and collect all valid strings at that level.

Wrong: Returned empty list on empty input or string without parentheses.✅ Return [""] for empty input and [input] if no parentheses present.

Wrong: (((((Failed to remove invalid parentheses when all are invalid.✅ Remove all invalid parentheses and return [""] if none remain valid.

Wrong: (())())()Removed parentheses multiple times or failed to prune duplicates.✅ Track indices of removals and prune duplicate states in recursion or BFS.

✓

Test Cases

Focus on handling empty and trivial inputs correctly before tackling edge cases.

Understand common pitfalls like greedy removal and duplicate pruning to handle corner cases.

Optimize your algorithm to handle large inputs efficiently using BFS and pruning.

t1_01basic

Input{"s":"()())()"}

Expected["()()()","(())()"]

⏱ Performance - must finish in 2000ms

Removing one invalid ')' at different positions yields two valid strings.

💡 Think about removing the minimum number of parentheses to balance the string.

💡 Use BFS or backtracking to generate all possible removals level by level.

💡 Stop at the first level where valid strings are found to ensure minimum removals.

Why it failed: Returned invalid strings or missed valid minimal removals. Fix by ensuring BFS stops at first valid level and collects all valid strings at that level.

✓ Correct minimal removals and all valid strings returned.

t1_02basic

Input{"s":"(a)())()"}

Expected["(a)()()","(a())()"]

⏱ Performance - must finish in 2000ms

Similar to canonical example but with letters; minimal removals yield two valid strings.

💡 Letters do not affect validity; only parentheses count.

💡 Check validity by counting parentheses ignoring letters.

💡 Apply BFS or backtracking similarly to find minimal removals.

Why it failed: Incorrectly removed letters or failed to consider letters as valid characters. Fix by only removing parentheses and ignoring letters in validity checks.

✓ Correctly handled letters and minimal removals.

t2_01edge

Input{"s":""}

Expected[""]

⏱ Performance - must finish in 2000ms

Empty string is valid; return list with empty string.

💡 Empty input should return itself as valid.

💡 Check if your code handles empty strings without error.

💡 Return [""] immediately if input is empty.

Why it failed: Returned empty list or error on empty input. Fix by handling empty input as valid and returning [""] directly.

✓ Correctly returns [""] for empty input.

t2_02edge

Input{"s":"abcde"}

Expected["abcde"]

⏱ Performance - must finish in 2000ms

String with no parentheses is already valid; return itself.

💡 If no parentheses, string is valid by default.

💡 Check validity function ignores letters correctly.

💡 Return original string in a list if no removals needed.

Why it failed: Incorrectly removed letters or returned empty list. Fix by skipping removal when no parentheses present.

✓ Correctly returns original string when no parentheses.

t2_03edge

Input{"s":"()()"}

Expected["()()"]

⏱ Performance - must finish in 2000ms

String with all valid parentheses; no removals needed.

💡 Check if input is already valid before removals.

💡 Avoid unnecessary removals if string is valid.

💡 Return input string in a list if valid.

Why it failed: Removed valid parentheses unnecessarily. Fix by validating input first and returning early if valid.

✓ Correctly returns input when already valid.

t3_01corner

Input{"s":"((((("}

Expected[""]

⏱ Performance - must finish in 2000ms

All parentheses are invalid; minimal removal is removing all to get empty string.

💡 Check if your code handles strings with only invalid '(' correctly.

💡 Minimal removal means removing all invalid parentheses.

💡 Return [""] when no valid parentheses remain.

Why it failed: Returned non-empty strings with invalid parentheses. Fix by removing all invalid parentheses and returning empty string if none valid.

✓ Correctly returns [""] when all parentheses are invalid.

t3_02corner

Input{"s":"()())())"}

Expected["()()()","(())()"]

⏱ Performance - must finish in 2000ms

Tests greedy trap: removing first invalid ')' only may miss other valid minimal removals.

💡 Greedy removal of first invalid parenthesis may miss other solutions.

💡 Use BFS level-by-level to find all minimal removals.

💡 Collect all valid strings at first valid removal level.

Why it failed: Returned only one valid string due to greedy removal. Fix by using BFS to explore all minimal removals at same level.

✓ Correctly returns all minimal valid strings.

t3_03corner

Input{"s":"(())())()"}

Expected["(())()()","(())()()"]

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 and unbounded removals; only remove each parenthesis once.

💡 Each parenthesis can be removed at most once.

💡 Avoid removing the same parenthesis multiple times in recursion.

💡 Use indices to track removals and avoid duplicates.

Why it failed: Removed same parenthesis multiple times causing duplicates or invalid results. Fix by tracking indices and pruning duplicates.

✓ Correctly handles 0/1 removal per parenthesis.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Input length n=100000; solution must run in O(n * 2^k) where k is minimal removals, optimized BFS or pruning required.

💡 Brute force exponential solutions will time out on large inputs.

💡 Use BFS with pruning and early stopping at first valid level.

💡 Avoid generating all subsequences; prune invalid paths early.

Why it failed: TLE due to exponential brute force without pruning. Fix by implementing BFS level-by-level with pruning and early stopping.

✓ Solution runs within time limit using BFS pruning.