LC32.md

Problem: Longest Valid Parentheses

Difficulty: Hard

Description:

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

Examples:

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

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

Constraints:

0 <= s.length <= 3 * 10^4
s[i] is '(', or ')'.

Solutions:

To solve this problem we can use the stack data strucutre to keep track of the current maximum length, and update the value with respect to what we have seen so far in the given string. The time and space complexity is O(N) where N is the length of s.

def longestValidParentheses(s):
    """
    :type s: str
    :rtype: int
    :Time Complexity: O(N)
    :Space Complexity: O(N)
    """
    stack = []
    ans = 0
    current = 0

    for char in s:
        if char == "(":
            stack.append(current)
            current = 0
        elif char == ")":
            if len(stack) > 0:
                val = stack.pop()
                current += val + 2
                ans = max(ans, current)
            else:
                current = 0
    return ans