32. Longest Valid Parentheses Leetcode Java

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:

Use a stack to track unpaired  left parentheses "(". 

1) If cur char is "(" push it to the stack

2) If cur char is ")" 

     a) stack is empty, which means there is no unpaired "(", so the cur ")" will be also unpaired. We use a variable last to keep track the last unpairable ")"

     b) stack is not empty, pop the "(" so now current  char ")" is paired with the popped "(" so the length of current valid Parentheses will be (1) . if stack is still not empty, length= curIndex- stack.peek(index). (2) if stack is empty, length= curIndex- last, because the next index of last will be the start index of this valid Parentheses.  

Time complexity: O(n)

 public int longestValidParentheses(String s) {  
    if(s==null || s.length()<2) return 0;  
    int ls=s.length();  
    int res=0;  
    int last=-1;  
    Stack<Integer> st=new Stack<Integer>();  
    for(int i=0;i<ls;i++){  
      if(s.charAt(i)=='(') st.push(i);  
      else {  
        if(st.isEmpty()) last=i;  
        else{  
            st.pop();  
            int l=(st.isEmpty())? i-last: i-st.peek();  
            res=Math.max(res,l);  
          }  
        }  
      }  
    return res;  
   }