# The Problem:

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.

# Notes:

- Wrong way: I was thinking of using stack, and each time find a pair then pop that pair. Then realized that the stack will only contain ‘(‘, since each time a ‘)’ come, instead of pushing it, a ‘(‘ will be popped. So I switched to only use a counter to record the number of ‘(‘. But consider this case: “(()()” and “()(()”, although they follow the same number of ‘(‘ and ‘)’, we need to record the location of unmatched ‘(‘ !
- Solution I: use a stack of integer to record the indices of unpaired ones. So each ‘(‘ will be pushed into stack, and for each ‘)’, if no ‘(‘ can match (stack empty, or stack top is a ‘)’ ), then also push into stack. otherwise pop a ‘(‘. In this fashion only peek the top can know the last unpaired index, by subtracting it we can get the valid length.
- Solution II: a less straight forward DP solution I found online. Use an array vlen to record the valid length of parentheses ending with s[i]. For each ‘(‘, it will have vlen[i] = 0; for each ‘)’, check the index of precous ‘free’ char, which is at j=(i-1-vlen[i-1]), see if it’s a ‘(‘, if true then can be paired, and vlen[i]=vlen[i-1]+2, and do NOT forget to also merge with vlen[j-1] !

# Java Solution I:

public class Solution { public int longestValidParentheses(String s) { // use a stack to record unpaired indices Stack<Integer> st = new Stack<Integer>(); int valid = 0; int max = 0; for(int i = 0; i < s.length(); i++){ // 1. it's a '(' ; 2. it's a ')' but no '(' left to match if(s.charAt(i)=='(' || st.empty()|| s.charAt(st.peek())==')'){ st.push(i); } else{ st.pop(); if(st.empty()){ // note here is i+1, not i ! valid = i+1; max = valid; } else{ valid = i-st.peek(); max = Math.max(max, valid); } } } return max; } }

# Java Solution II:

public class Solution { public int longestValidParentheses(String s) { if(s.length()==0)return 0; //valid length ending at i int[] vlen = new int[s.length()]; vlen[0]= 0; int max = 0; for(int i = 1; i < s.length(); i++){ if(s.charAt(i)=='('){ // valid parenthese cannot end with '(' vlen[i] = 0; } else{ int j = i-1-vlen[i-1]; //can match with a previous '(' if(j>=0 && s.charAt(j)=='('){ vlen[i] = vlen[i-1]+2; // connect with the length before j if(j-1>=0){ vlen[i] += vlen[j-1]; } } } max = Math.max(max, vlen[i]); } return max; } }