# Share my java solution with stack and DP

• Stack:

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

DP:

``````public int longestValidParentheses(String s) {
/*max[i] = j means subsequence index i-j is longest valid Parentheses*/
int[] max = new int[s.length()+1];
max[s.length()] = s.length();
int sum = 0;
for(int i=s.length()-1;i>=0;i--){
if(max[i+1]!=i+1){
if(max[i+1]+1<s.length()&&s.charAt(i)=='('&&s.charAt(max[i+1]+1)==')'){
max[i] = (max[i+1]+2<s.length()+1&&max[max[i+1]+2]!=max[i+1]+2)?max[max[i+1]+2]:max[i+1]+1;
}
else    max[i] = i;
}
else if(i+1<s.length()&&s.charAt(i+1)==')'&&s.charAt(i)=='('){
max[i] = (i+2<s.length()+1&&max[i+2]!=i+2)?max[i+2]:i+1;
}
else    max[i] = i;
sum = Math.max(sum, max[i]-i+1);
}
return (sum==1)?0:sum;
}``````

• I really like your clear and elegant solution:
But could you elaborate a bit more on this line please:
max = Math.max(max, i - ((stack.isEmpty())? - 1:stack.peek()));
I don't fully get it.
Thanks!

• After pop(), it can be empty, which means that s.substring(0,i+1) is valid so we need i-(-1); if not empty, s.substring(st.peek(),i+1) will be valid.

• Great response! Thanks a lot!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.