Check for valid parentheses nesting I found this question on leetcode and that was my answer ... But someone told me it's too bad that it takes \$O(n^3)\$ I am not sure that it takes all that time ... and trying to find better understandable Javascript solution.


  Given a string containing just the characters '(', ')', '{', '}', '['
  and ']', determine if the input string is valid. The brackets must
  close in the correct order, "()" and "()[]{}" are all valid but "(]"
  and "([)]" are not.




/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    while (s.length != 0 &amp;&amp; s.includes("[]") || s.includes("()") || s.includes("{}")) {
        s = s.replace("[]", "");
        s = s.replace("()", "");
        s = s.replace("{}", "");
    }
    return s.length &lt; 1
};


console.log(isValid("({(())})")); // True
console.log(isValid("({((}))})")); // False
Your friend's assertion that it's \$O(n^3)\$ is questionable. For that to be true, either or both of the replace or includes function needs to be \$O(n^2)\$ which is ... unlikely. It's more likely that both are \$O(mn)\$ complexity where m is the length of the source string, and n is the length of the search string ([] or {} or () all of which are "short")

Putting aside the complexity, it is still apparent that your code is not very efficient, even at \$O(n^2)\$.

An \$O(n)\$ solution is possible if you use a state machine and a stack (or recursion) to control the assertions. After any open parenthesis only 4 characters can follow, another open parenthesis ((, [, or {), or the matching close parenthesis. You can simplify the state machine by adding a dummy character, I'll use a . period to illustrate:



const terminator = ".",
    openers = "{[(",
    following = {
        "[": "]",
        "{": "}",
        "(": ")",
    };

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {

    // add terminating character.
    s = s + terminator;

    // seed stack with 
    const stack = [terminator];

    for (const c of s) {
        if (openers.includes(c)) {
            // going deeper in to nesting.
            stack.push(following[c]);
        } else {
            // coming out of nesting, check the correct closer.
            // (which may be a "." at the end)
            if (stack.pop() != c) {
                return false;
            }
        }
    }
    return true;

};


console.log(isValid("({(())})")); // True
console.log(isValid("({((}))})")); // False