JavaScript solution, O(n) with comments
\n/**\n * @param {string} s\n * @return {number}\n */\nvar longestValidParentheses = function(s) {\n    if (!s || !s.length) { return 0; }\n\n    /* We will sto
```\n/**\n * @param {string} s\n * @return {number}\n */\nvar longestValidParentheses = function(s) {\n    if (!s || !s.length) { return 0; }\n\n    /* We will store the position of every invalid parenthesis.\n       Once we have that, the solution is simply the longest\n       subarray between two invalid parentheses */\n    const invalids = new Set();\n\n    /* We stack the opening parentheses as we find them,\n       and pop them we we meet the corresponding closing\n       parenthesis. Note that a closing ) always matches the\n       latest opening ( one, hence the choice of a stack */\n    const stack = [];\n\n    for (let i=0; i<s.length; i++) {\n        if (s[i] === '(') {\n            stack.push(i);\n        } else {\n            // If we are closing an opening parenthesis, pop it out\n            if (stack.length) {\n                stack.pop();\n            } else {\n                /* Otherwise there is nothing to close,\n                   hence this parenthesis is invalid */\n                invalids.add(i);\n            }\n        }\n    }\n\n    /* Any remaining opening parenthesis that has not been closed is\n       automatically invalid */\n    while (stack.length) {\n        invalids.add(stack.pop());\n    }\n    \n    // Here we just count how many valid in between every invalid\n    let max = 0, count = 0;\n    for (let i=0; i<=s.length; i++) {\n        if (i < s.length && !invalids.has(i)) {\n            count++;\n        } else {\n            max = Math.max(max, count);\n            count = 0;\n        }\n    }\n    return max;\n};\n```
[]