Longest Valid Parentheses [Hard] — Stack / DP

Problem Statement

Given a string of ( and ), find the length of the longest valid parentheses substring.

Input: "(()"    → Output: 2
Input: ")()())" → Output: 4

Intuition

Stack approach: Push indices. Initialize stack with [-1] as base. For each (, push index. For each ), pop; if stack empty, push current index as new base; else update ans = i - stack.top().

Solutions

C++

int longestValidParentheses(string s) {
    stack<int> stk; stk.push(-1);
    int ans=0;
    for (int i=0;i<s.size();i++) {
        if(s[i]=='(') stk.push(i);
        else {
            stk.pop();
            if(stk.empty()) stk.push(i);
            else ans=max(ans,i-stk.top());
        }
    }
    return ans;
}

Java

public int longestValidParentheses(String s) {
    Deque<Integer> stk=new ArrayDeque<>(); stk.push(-1);
    int ans=0;
    for(int i=0;i<s.length();i++){
        if(s.charAt(i)=='(') stk.push(i);
        else{stk.pop();if(stk.isEmpty())stk.push(i);else ans=Math.max(ans,i-stk.peek());}
    }
    return ans;
}

JavaScript

var longestValidParentheses = function(s) {
    const stk=[-1]; let ans=0;
    for(let i=0;i<s.length;i++){
        if(s[i]==='(') stk.push(i);
        else{stk.pop();if(!stk.length)stk.push(i);else ans=Math.max(ans,i-stk.at(-1));}
    }
    return ans;
};

Python

def longestValidParentheses(s: str) -> int:
    stack = [-1]
    ans = 0
    for i, c in enumerate(s):
        if c == '(':
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)
            else:
                ans = max(ans, i - stack[-1])
    return ans

Complexity

Time: O(n)
Space: O(n)