Problem Description

Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.

Example 1

Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Example 2

Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".

Solution

The first thought is that for a valid parentheses, the open and closed brackets must be the same, in addition, when we scan through from left to right, the number of open brackets should be always no smaller than that of closed brackets. Whenever we find such a string, this is the valid parentheses. Therefore, we can have two counters to record the number of brackets. Whenever the number of open brackets is smaller, we know we're done with the part before this position since this part cannot be combined with later part to have a valid parenthesis, and we have to reset counters. However, this method will also find ((()) invalid, since the method basically requires the string must start from the position where we reset/set counters zero. To overcome this, we can next scan through from right to left and require the number of closed brackets should always be larger or equal.

The second idea is built on the above method. Again, the above method requires that the string must start from the position where we reset/set counters zero, since we are counting all brackets from this position with two counters. To overcome this, the other way is to record positions of open/closed brackets when we scan. We put down positions of all open brackets, while for closed brackets, we check if we have available open brackets and wipe off the recent open bracket, then note down the length of this valid parenthesis. If there're no available open brackets on our note, this means we have more closed brackets so far, and this part can be discarded, but we have to write down the position of this closed brackets so that we know where the new possible string will start.

The third solves the problem from another perspective: given a valid parenthesis s, how we can construct another? We can have s() and (s), or ()s. Now we have an iteration, DP can be used. Suppose dp[i] means the length of longest valid parentheses which ends at index i-1, the hard part is how to calculate dp[i+1] given dp[i]? From the three possible forms s(), (s) and ()s, first we know s[i] must be ) to be possibly valid. And we check s[i-1], if it is (, we know the form will be s(), that is dp[i+1]=dp[i-1]+2. If s[i-1]=), then the form (s) is the case, that is if s[i-dp[i]-1]='(' then dp[i+1]=dp[i]+2, however do not forget any possible parentheses before i-dp[i]-1 since s1(s) is also valid.

Java Code

Two Counters

class Solution {
    public int longestValidParentheses(String s) {
        int len = s.length(), res=0;
        int left = 0, right = 0;
        for(int i=0; i<len; i++){
            int c = s.charAt( i );
            if( c=='(' ) left++;
            else right++;
            if(left == right) res = Math.max(res, left+right);
            if(left < right) left = right = 0;
        }
        left = right = 0;
        for(int i=len-1; i>=0; i--){
            int c = s.charAt( i );
            if( c=='(' ) left++;
            else right++;
            if(left == right) res = Math.max(res, left+right);
            if(left > right) left = right = 0;
        }
        return res;
    }
}

Stack

class Solution {
    public int longestValidParentheses(String s) {
        int len = s.length(), res=0;
        Stack<Integer> stk = new Stack<>();
        stk.push(-1);
        for(int i=0; i<len; i++){
            char c = s.charAt(i);
            if(c=='(') stk.push(i);
            else{
                stk.pop();
                if( !stk.isEmpty() ) res = Math.max(res, i-stk.peek());
                else stk.push(i);
            }
        }
        return res;
    }
}

DP

class Solution {
    public int longestValidParentheses(String s) {
        int len = s.length(), res=0;
        if( len==0 ) return 0;
        int[] dp = new int[len];
        for(int i=1; i<len; i++){
            char c = s.charAt( i );
            if( c == '(' ) continue;
            if( s.charAt(i-1)=='(' ) dp[i] = (i-2>=0 ? dp[i-2] : 0) + 2;
            else if( i-dp[i-1]-1>=0 && s.charAt(i-dp[i-1]-1) == '(' ) 
                dp[i] = dp[i-1] + 2 + (i-dp[i-1]-2>=0 ? dp[i-dp[i-1]-2] : 0);
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}