32. Longest Valid Parentheses

• Difficulty: Hard

• Topics: String, Dynamic Programming

• Similar Questions:

  • Valid Parentheses

Problem:

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

Solutions:

class Solution { //gready method need to consider two scenarios
                // example "(()"
public:
    int longestValidParentheses(string s) {
        string reversed = s;
        reverse(reversed.begin(), reversed.end());
        replace(reversed.begin(), reversed.end(), '(', '=');
        replace(reversed.begin(), reversed.end(), ')', '(');
        replace(reversed.begin(), reversed.end(), '=', ')');


        return max(longestValidParenthesesHelper(s), longestValidParenthesesHelper(reversed));
    }

    int longestValidParenthesesHelper(string s) {
        int ret = 0;
        int balance = 0;
        int left = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (s[i] == '(') {
                ++balance;
            } else {
                --balance;
                if (balance == 0) {
                    ret = max(ret, i - left + 1);
                } else if (balance < 0) {
                    left = i + 1;
                    balance = 0;
                }
            }
        }

        return ret;
    }

};

More concise solution

Stack solution from Huahua

// Author: Huahua
class Solution {
public:
  int longestValidParentheses(string s) {
    stack<int> q;
    int start = 0;
    int ans = 0;
    for (int i = 0;i < s.length(); i++) {
      if(s[i] == '(') {
        q.push(i);
      } else {
        if (q.empty()) {
          start = i + 1;
        } else {
          int index = q.top(); q.pop();
          ans = max(ans, q.empty() ? i - start + 1 : i - q.top());          
        }
      }
    }
    return ans;
  }
};

DP solution from Xishuashua

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size(), maxLen = 0;
        vector<int> dp(n+1,0);
        for(int i=1; i<=n; i++) {
            int j = i-2-dp[i-1];
            if(s[i-1]=='(' || j<0 || s[j]==')') 
                dp[i] = 0;
            else {
                dp[i] = dp[i-1]+2+dp[j];
                maxLen = max(maxLen, dp[i]);
            }
        }
        return maxLen;
    }
};