32

32. Longest Valid Parentheses (Hard)

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 "()()"

Related Topics:
String, Dynamic Programming

Similar Questions:

• Valid Parentheses (Easy)

Solution 1. DP

Let dp[i + 1] be the length of the longest valid parentheses ending at s[i].

When s[i] == ')':

dp[i + 1] = dp[i] + 2 + dp[start]   If s[start] == '('
          = 0                       If s[start] != '('
          where start = i - dp[i] - 1

When s[i] == '(':

dp[i + 1] = 0

Trivial case:

dp[0] = 0

The answer is the max value in dp array.

// OJ: https://leetcode.com/problems/longest-valid-parentheses/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int longestValidParentheses(string s) {
        vector<int> dp(s.size() + 1, 0);
        int ans = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(') continue;
            int start = i - dp[i] - 1;
            if (start >= 0 && s[start] == '(')
                dp[i + 1] = dp[i] + 2 + dp[start];
            ans = max(ans, dp[i + 1]);
        }
        return ans;
    }
};

Solution 2. Stack

We try to leave invalid parentheses in the stack st.

• If s[i] == '(', we push it into stack
• If s[i] == ')':
  • If s[st.top()] == '(', then st.top() is a valid left parenthesis, we pop it. The length of the parenthesis string we just formed is i - st.top().
  • otherwise, this s[i] can't form a valid parenthesis. Push it into stack.

// OJ: https://leetcode.com/problems/longest-valid-parentheses/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> st;
        st.push(-1);
        int ans = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == ')' && st.top() != -1 && s[st.top()] == '(') {
                st.pop();
                ans = max(ans, i - st.top());
            } else st.push(i);
        }
        return ans;
    }
};

Solution 3. Counters

// OJ: https://leetcode.com/problems/longest-valid-parentheses/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
// Ref: https://leetcode.com/problems/longest-valid-parentheses/solution/
class Solution {
public:
    int longestValidParentheses(string s) {
        int left = 0, right = 0, ans = 0, N = s.size();
        for (int i = 0; i < N; ++i) {
            left += s[i] == '(';
            right += s[i] == ')';
            if (left == right) ans = max(ans, left + right);
            else if (right > left) left = right = 0;
        }
        left = 0, right = 0;
        for (int i = N - 1; i >= 0; --i) {
            left += s[i] == '(';
            right += s[i] == ')';
            if (left == right) ans = max(ans, left + right);
            else if (left > right) left = right = 0;
        }
        return ans;
    }
};