Longest Valid Parentheses

Leetcode Problem 32: Longest Valid Parentheses

Problem Summary

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

Constraints:

• The string has between 0 and 30,000 characters.
• Each character is either '(' or ')'.

Techniques

• String
• Dynamic Programming
• Stack

Solution

function longestValidParentheses(s: string): number {
    let maxLen = 0
    let stack: number[] = [-1]

    for (let i = 0; i < s.length; i++) {
        let parenthesis = s.charAt(i)

        if (parenthesis === '(') { 
            stack.push(i)
        } else {
            stack.pop()

            if (stack.length === 0) {
                stack.push(i)
            } else {
                maxLen = Math.max(i - stack[stack.length - 1], maxLen)
            }
        }
    }

    return maxLen
};

console.log(longestValidParentheses(")()())"))
console.log(longestValidParentheses("(()"))