Interview Question - Remove Invalid Parentheses - JavaScript

remove_invalid_parentheses.js

/**
 Interviwer asks: An expression will be given which can contain open and close parentheses and
 optionally some characters, No other operator will be there in string. We need to remove the minimum
 number of parentheses to make the input string valid. If more than one valid output is possible 
 removing the same number of parentheses, then print all such output possibilities.
  */

function isValidString(s) {
    var count = 0;
    for (let c of s) {
        if (c === '(') {
            count++;
        }
        else if (c === ')') {
            count--;
        }
        if (count < 0) return false;
    }
    return count === 0;
}

function removeInvalidParentheses(s) {
    let levels = [s];
    while (true) {
        let valid = levels.filter(isValidString);
        if (valid.length > 0) {
            return new Set(valid);
        }

        // check validity of all possible substrings with one character removed.
        let nextlevels = [];
        for (let s of levels) {
            for (let i = 0; i < s.length; i++) {
                nextlevels.push(s.substring(0, i) + s.substring(i + 1));
            }
        }
        levels = nextlevels;
    }
}

console.log(removeInvalidParentheses(')()()('));
console.log(removeInvalidParentheses('(()))'));
console.log(removeInvalidParentheses(')('));
console.log(removeInvalidParentheses('()))(()'));
console.log(removeInvalidParentheses('(()())'));

My solutions was;

/**
 * @param {string} s
 * @return {string[]}
 */
var removeInvalidParentheses = function(s) {
    // Check input parentheses are valid
    const isValid = (p) => {
        if (p[0] === ")") return false;
        if (p[p.length -1] === "(") return false;
        
        let counter = 0;
        
        for (let i=0; i<p.length; i++) {
            if (p[i] === "(") counter++;
            if (p[i] === ")") counter--;
        }
        
        return counter === 0;
    };
    
    if (isValid(s)) return s;
    
    let collection = new Set();
    
    for (let i = 0; i<s.length; i++) {
        let p;
        if (i===0) {
            p = s.slice(1,s.length);
        } else {
            
        }
        p = s.slice(0,i) + s.slice(i+1,s.length);
        
        if (isValid(p)) {
            collection.add(p);
        }
    }
    
    return Array.from(collection);
};