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.

DP solution
I like this solution very much!

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        vector<int> len(n, 0);
        stack<int> index_s;
        int maxlen = 0;
        for ( int i = 0; i <= n-1; i++ ) {
            if ( s[i] == ')' and index_s.empty() ) continue;
            if ( s[i] == '(' ) {
                index_s.push(i);
                continue;
            }
            int j = index_s.top();
            index_s.pop();
            if ( j == 0 ) len[i] = i+1;
            else len[i] = len[j-1] + i-j+1;
            maxlen = max(maxlen, len[i]);
        }
        return maxlen;
    }
};

Notes
DP solution Use an array len to record the length of valid parentheses ending at i-th position.

• If s[i] == '(', it can't be the ending. So len[i] = 0.
• If s[i] == ')' and there is no '('in the stack, it is not a valid parenthesis. So len[i] = 0.
• If s[i] == ')' and it pairs with s[j] = '(', it can be proved that s.substr(j, i-j+1) is a valid parenthesis whose length is j-i+1. Thus len[i] = len[j-1] + j-i+1.
  • Proof:
    If s.substr(j, i-j+1) is not a valid parenthesis, there must be an unpaired '(' or ')'. We assume that this unparied character is s[j'], j < j' < i. If s[j'] == '(', then s[i] must pair with it; If s[j'] == ')', then s[j] mus pair with it. It is not possible that s[j] and s[i] forms a pair.