Bird
Raised Fist0
Interview PrepbacktrackinghardFacebookAmazonGoogle

Remove Invalid Parentheses

Choose your preparation mode3 modes available
📋
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
}
0/9
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
t1_01basic
Input{"s":"()())()"}
Expected["()()()","(())()"]

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

t1_02basic
Input{"s":"(a)())()"}
Expected["(a)()()","(a())()"]

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

t2_01edge
Input{"s":""}
Expected[""]

Empty string is valid; return list with empty string.

t2_02edge
Input{"s":"abcde"}
Expected["abcde"]

String with no parentheses is already valid; return itself.

t2_03edge
Input{"s":"()()"}
Expected["()()"]

String with all valid parentheses; no removals needed.

t3_01corner
Input{"s":"((((("}
Expected[""]

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

t3_02corner
Input{"s":"()())())"}
Expected["()()()","(())()"]

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

t3_03corner
Input{"s":"(())())()"}
Expected["(())()()","(())()()"]

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

t4_01performance
Input{"_description":"n=100000 at constraint boundary - executor generates this"}
⏱ 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.