0032. Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find 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 "()()".

Example 3:

Input: s = ""
Output: 0

Constraints:

• 0 <= s.length <= 3 * 104
• s[i] is '(', or ')'.

Analysis

1. dp[i]: longest valid parentheses length ending with current [i]
2. i - dp[i] + 1: start index of the previous valid one (dp[i-1])
3. why +2 : because the dp[prevStart-1] + ( + dp[i-1] + ), there are two elements

Code

 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] == ')'){
            /* this block could be ignored because the else block has already calculated it
            if(s[i-1] == '('){ // valid parethese with previous one
                longest[i] = (i-2) >= 0 ? (longest[i-2] + 2) : 2;
                curMax = max(longest[i],curMax);
            }
            */
            else{ // if s[i-1] == ')', combine the previous length.
                int prevStart = i - longest[i-1] - 1; // the one before the last start valid
                if(prevStart >= 0 && s[prevStart] == '('){
                    longest[i] = longest[i-1] + 2 + ((prevStart - 1 >= 0)?longest[prevStart - 1]:0);
                    curMax = max(longest[i],curMax);
                }
            }
        }
        //else if s[i] == '(', skip it, because longest[i] must be 0
    }
    return curMax;
}

---

Last update: April 1, 2022