Longest Valid Parentheses

Problem Description

Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Example 2:

Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".

Example 3:

Input: s = ""
Output: 0

Constraints:

• 0 <= s.length <= 3 * 104
• s[i] is '(', or ')'.

Solution (JavaScript)

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function(s) {
    let n = s.length, longest = 0;
    let st = [];
    for (let i = 0; i < n; i++) {
        if (s[i] == '(') {
            st.push(i);
        } else {
            if (st.length) {
                if (s[st[st.length-1]] == '(') st.pop();
                else st.push(i);
            } else {
                st.push(i);
            }
        }
    }
    if (!st.length) {
        longest = n;
    } else {
        let a = n, b = 0;
        while (st.length) {
            b = st[st.length-1];
            st.pop();
            longest = Math.max(longest, a - b - 1);
            a = b;
        }
        longest = Math.max(longest, a);
    }
    return longest;
};