Remove_Invalid_Parentheses.js

/*
Remove Invalid Parentheses
https://leetcode.com/problems/remove-invalid-parentheses/

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Example 1:

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

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

Input: ")("
Output: [""]
*/

/**
 * @param {string} s
 * @return {string[]}
 */
var removeInvalidParentheses = function(s) {
  var queue = [];
  var visited = new Set();
  queue.push(s);
  var result = [];
  var found = false;
    
  while(queue.length !== 0) {
    var str = queue.shift();
    if(isValid(str)) {
      result.push(str);
      found = true;
    } else if(!found){   
      for(var i = 0; i < s.length; i++) {
        if(str[i] === "(" || str[i] === ")") {
          var subStr = str.slice(0, i) + str.slice(i + 1, s.length);
          if(!visited.has(subStr)) {
            queue.push(subStr);   
            visited.add(subStr);
          }
        }    
      }
    }
  }
  
  return result;
};

var isValid = function(s) {
  var leftCount = 0;
  var iter = 0;
  while(iter < s.length) {
    if(s[iter] === "(") 
      leftCount++;
    else if(s[iter] === ")") {
      leftCount--;
      if(leftCount < 0)
        return false;
    }
    iter++;
  }    
  
  return leftCount === 0;
}

module.exports.removeInvalidParentheses = removeInvalidParentheses;