Remove minimum invalid parentheses

Hard

Problem

Remove the minimum number of parentheses to make the string valid, and return every distinct valid result. The string may also contain letters.

Example 1

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

Example 2

Input:  "(a)())()"
Output: ["(a())()", "(a)()()"]

Also asked as: Remove Invalid Parentheses

Test cases

Case 1

Input:    "()())()"
Expected (any order): ["(())()","()()()"]

Case 2

Input:    "(a)())()"
Expected (any order): ["(a())()","(a)()()"]

Case 3

Input:    "()"
Expected (any order): ["()"]

Case 4

Input:    ")("
Expected (any order): [""]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. BFS by removal count

Time O(2ⁿ) worstSpace O(2ⁿ)

Level 0 = the original string; each level removes one character. Return all valid strings from the first level that contains any — that is the minimum number of removals.

function removeInvalidParentheses(s) {
const isValid = (str) => {
let bal = 0;
for (const c of str) {
if (c === '(') bal++;
else if (c === ')' && --bal < 0) return false;
}
return bal === 0;
};
let level = new Set([s]);
while (level.size) {
const valid = [...level].filter(isValid);
if (valid.length) return valid;
const next = new Set();
for (const str of level)
for (let i = 0; i < str.length; i++)
if (str[i] === '(' || str[i] === ')') next.add(str.slice(0, i) + str.slice(i + 1));
level = next;
}
return [''];
}