# 32. Longest Valid Parentheses

###### tags: `leetcode`,`stack`,`dp`,`hard`

>ref: https://leetcode.com/problems/longest-valid-parentheses/
>
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.


>1. stack紀錄不成對項目,最後判斷該組兩兩隻間距 最大者為解
>2. time O(N) space O(N)

    public int longestValidParentheses(String s) {
        
        Stack<Integer> st= new Stack<>();
        
        int n=s.length();
        
        int pre=n;
        int cur;
        
        int len=0;
        
        for(int i=0;i<n;i++){
            if(st.isEmpty()){
                st.add(i);
            }else{
                if(s.charAt(i)==')' && s.charAt(st.peek())=='('){
                    st.pop();
                }else{
                    st.add(i);
                }
            }
        }
        
        if(st.isEmpty()){
            return n;
        }else{
            while(!st.isEmpty()){
                cur=st.pop();
                len=Math.max(len,pre-cur-1);
                pre=cur;
            }
            len=Math.max(len,pre);
            return len;
            
        }
        
    }

## dp
https://leetcode.com/problems/longest-valid-parentheses/discuss/14133/My-DP-O(n)-solution-without-using-stack
And the DP idea is :

If s[i] is '(', set longest[i] to 0,because any string end with '(' cannot be a valid one.

Else if s[i] is ')'

If s[i-1] is '(', longest[i] = longest[i-2] + 2

Else if s[i-1] is ')' and s[i-longest[i-1]-1] == '(', longest[i] = longest[i-1] + 2 + longest[i-longest[i-1]-2]

For example, input "()(())", at i = 5, longest array is [0,2,0,0,2,0], longest[5] = longest[4] + 2 + longest[1] = 6.

    public int longestValidParentheses(String s) {
    
        char[] ch= s.toCharArray();
        
        int n = ch.length;
        int max=0;
        
        int preidx=0;
        
        int[] ans= new int[n];
        
        for(int i=1;i<n;i++){
            preidx=i-ans[i-1];
            if(ch[i]==')'){
                if(ch[i-1]=='('){
                    ans[i]=(i-2)>=0? ans[i-2]+2:2;
                }else if(preidx-1 >=0 && ch[preidx-1]=='('){
                    ans[i]=ans[i-1]+2+(preidx-2>=0? ans[preidx-2]:0);
                }
                max=Math.max(max,ans[i]);
            }
            
        }
        return max;
    }