Remove minimum invalid parentheses
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): [""]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 [''];}