Longest Valid Parentheses

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

For “(()”, the longest valid parentheses substring is “()”, which has length = 2.

Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4.

Solution:

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