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.
public class Solution { public int longestValidParentheses(String s) { // Start typing your Java solution below // DO NOT write main() function int max = 0 ; Stack<Integer> left = new Stack<Integer>(); Stack<Integer> right = new Stack<Integer>(); for(int i = 0 ; i<s.length(); i++){ if(s.charAt(i) == '('){ left.push(i); } else{ if(!left.isEmpty()){ left.pop(); } else{ right.push(i); } } } if(left.isEmpty()&&right.isEmpty()){ return s.length(); } int prev = s.length(), cur = 0; while(!left.isEmpty()){ cur = left.pop(); if(max < prev - cur -1){ max = prev - cur -1; } prev = cur; } while(!right.isEmpty()){ cur = right.pop(); if(max < prev - cur -1){ max = prev - cur -1; } prev = cur; } if(max < cur){ max = cur; } return max; } }
learned: number in stack is the distance for valid parentheses prev = cur is the action to move between valid parentheses
public class Solution { public int longestValidParentheses(String s) { int max = 0 ; Stack<Integer> left = new Stack<Integer>(); Stack<Integer> right = new Stack<Integer>(); int last = -1; for(int i = 0 ; i<s.length(); i++){ if(s.charAt(i) == '('){ left.push(i); } else{ if(!left.isEmpty()){ left.pop(); if(left.isEmpty()){ max = Math.max(max,i-last); } else{ max = Math.max(max,i-left.peek()); } } else{ last = i; } } } return max;