32. 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: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

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

Solution

Approach 1: Stack.

Approach 2: DP.

Approach 3: Traverse from left to right and then from right to left.

Code (Python)

Approach 1:

Approach 2:

Approach 3:

Code (C++)

Approach 1:

// Stack.
// Need to use stack, since we need to distinguish, e.g., "()(()" and "(()()".
class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> st;
        for (int i = 0; i < s.size(); ++i)
        {
            if (s[i] == ')' && !st.empty() && s[st.top()] == '(')
                st.pop();
            else
                st.push(i);
        }
        int prev = s.size();
        int maxLen = 0;
        while (!st.empty())
        {
            maxLen = std::max(maxLen, prev - st.top() - 1);
            prev = st.top();
            st.pop();
        }
        maxLen = std::max(maxLen, prev);
        return maxLen;
    }
};

Approach 2:

// DP.
class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        if (n == 0)
            return 0;
        vector<int> len(n, 0); // the length of the longest valid string ends with s[i]
        int maxLen = 0;
        for (int i = 1; i < n; ++i)
        {
            if (s[i] == ')')
            {
                int j = i - 1 - len[i-1];
                if (j >= 0 && s[j] == '(')
                {
                    len[i] = len[i-1] + 2;
                    if (j - 1 >= 0)
                        len[i] += len[j-1];
                    maxLen = std::max(maxLen, len[i]);
                }
            }
        }
        return maxLen;
    }
};

Approach 3:

// Traverse from left to right and then from right to left.
class Solution {
public:
    int longestValidParentheses(string s) {
        int left = 0;
        int right = 0;
        int maxLen = 0;
        for (int i = 0; i < s.size(); ++i)
        {
            if (s[i] == '(')
                left++;
            else
                right++;
            if (left == right)
                maxLen = std::max(maxLen, right * 2);
            else if (right > left)
            {
                left = 0;
                right = 0;
            }
        }
        left = 0;
        right = 0;
        for (int i = s.size() - 1; i >= 0; --i)
        {
            if (s[i] == '(')
                left++;
            else
                right++;
            if (left == right)
                maxLen = std::max(maxLen, right * 2);
            else if (left > right) // not "else if (right > left)".
            {
                left = 0;
                right = 0;
            }
        }
        return maxLen;
    }
};