301. Remove Invalid Parentheses

Problem

Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.

Return all the possible results. 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.

Solution

/**
 * @param {string} s
 * @return {string[]}
 */
var removeInvalidParentheses = function(s) {
  const ans = [];
  const [left, right] = countInvalidParens();
  backtrack(s, 0, left, right);
  return ans;

  function countInvalidParens() {
    let left = 0, right = 0;
    for (const char of s) {
      left += char == "(";
      left == 0 ? right += char == ")" : left -= char == ")";
    }
    return [left, right];
  }

  function backtrack(str, start, left, right) {
    if (!left && !right) {
      if (isValid(str)) ans.push(str);
      return;
    }
    for (let i = start; i != str.length; i += 1) {
      if (i != start && str[i] == str[i-1]) continue;
      if (right > 0) {
        if (str[i] != ")") continue;
        backtrack(str.substr(0, i) + str.substr(i+1), i, left, right-1);
      } else {
        if (str[i] != "(") continue;
        backtrack(str.substr(0, i) + str.substr(i+1), i, left-1, right);
      }
    }
  };

  function isValid(str) {
    let count = 0;
    for (const char of str) {
      if (char == "(") count += 1;
      if (char == ")") count -= 1;
      if (count < 0) return false;
    }
    return count == 0;
  };
};

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).