32. Longest Valid Parentheses

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.

Thoughts:

1. Use stack to keep track of "non parenthesis" index. After the scan, calculate the largest number of parenthesis characters by calculating gaps between tracked indices.

2. DP: I construct a array longest[] , for any longest[i], it stores the longest length of valid parentheses which is end at i.If s[i] is '(', set longest[i] to 0,because any string end with '(' cannot be a valid one.Else if s[i] is ')'If s[i-1] is '(', longest[i] = longest[i-2] + 2 Else if s[i-1] is ')'and s[i-longest[i-1]-1] == '(', longest[i] = longest[i-1] + 2 + longest[i-longest[i-1]-2]. For example, input "()(())", at i = 5, longest array is [0,2,0,0,2,0], longest[5] = longest[4] + 2 + longest[1] = 6.jerryrcwong's post

Code

class Solution {
public:
    int longestValidParentheses(string s) {
        int len = s.length(), answer = 0;
        if(len == 0) return answer;
        stack<int> st; 
        for(int i =0 ; i < len; i++){
            if(s[i] == '(') st.push(i);
            else if(!st.empty() && s[st.top()]=='(') {
                st.pop();
            }
            else st.push(i);
        }

        if(st.empty()) return len;

        // find longest index gaps in st
        int end = len, start = 0; // here end = len is because we need to 
        // manually figure out the first case : end - start - 1 = # of complete parentheses characters in between two neighboring indices,
        // so to be consistent initial position end here is one postition 1 over the last element in the element as if there is an "virtual"
        // ')' in the end.

        while(!st.empty()){
            start = st.top(); st.pop();
            answer = max(answer, end - start - 1);
            end = start;
        }
        answer = max(answer, end); // compare the number of parenthesis character skiped till the first index, do not need extra "-1" since 
        // there is no start index any more (or the "virtual" starting index is at -1)
        cout<<end<<endl;
        return answer;
    }
};

Code: DP

  int longestValidParentheses(string s) {
            if(s.length() <= 1) return 0;
            int curMax = 0;
            vector<int> longest(s.size(),0);
            for(int i=1; i < s.length(); i++){
                if(s[i] == ')'){
                    if(s[i-1] == '('){
                        longest[i] = (i-2) >= 0 ? (longest[i-2] + 2) : 2;
                        curMax = max(longest[i],curMax);
                    }
                    else{ // if s[i-1] == ')', combine the previous length.
                        if(i-longest[i-1]-1 >= 0 && s[i-longest[i-1]-1] == '('){
                            longest[i] = longest[i-1] + 2 + ((i-longest[i-1]-2 >= 0)?longest[i-longest[i-1]-2]:0);
                            curMax = max(longest[i],curMax);
                        }
                    }
                }
                //else if s[i] == '(', skip it, because longest[i] must be 0
            }
            return curMax;
        }

Python

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s) < 1: return 0
        res, dp = 0, [0] * len(s)

        for i in range(1, len(s)):
            if s[i] == ')':
                if s[i- 1] == '(':
                    dp[i] = dp[i - 2] + 2 if i >= 2 else 2
                    res=  max(res, dp[i])

                elif s[i - 1] == ')' and i - 1 - dp[i - 1] >= 0 and s[i - 1 - dp[i - 1]] == '(':
                    dp[i] = dp[i-1] + 2 + (dp[i-2-dp[i-1]] if i-2-dp[i-1] >= 0 else 0)
                    res = max(res, dp[i])

        return res

Special thanks: LeetCode Discussion Forum for the reference!