301. Remove Invalid Parentheses

Description

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.

 

Example 1:

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

Example 2:

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

Example 3:

Input: s = ")("
Output: [""]

 

Constraints:

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

 

Solutions

Solution: Breadth-First Search

• Time complexity: O(2ⁿ)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {string} s
 * @return {string[]}
 */
const removeInvalidParentheses = function (s) {
  const isValid = str => {
    let left = 0;

    for (const char of str) {
      if (char === '(') left += 1;
      if (char === ')') left -= 1;
      if (left < 0) return false;
    }
    return left === 0;
  };

  if (isValid(s)) return [s];
  const result = [];
  let queue = new Set([s]);

  while (queue.size) {
    const next = new Set();

    for (const str of queue) {
      for (let index = 0; index < str.length; index++) {
        const current = str[index];

        if (current !== '(' && current !== ')') continue;
        const substr = `${str.slice(0, index)}${str.slice(index + 1)}`;

        if (next.has(substr)) continue;
        if (isValid(substr)) result.push(substr);
        next.add(substr);
      }
    }
    if (result.length) return result;
    queue = next;
  }
  return [];
};