Challenge Description

https://leetcode.com/problems/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 "()()"

Naive Solution

To get the longest valid parentheses, we could enumerate all the substring of input, and check each substring whether is a valid parenthese.

The overall time complexity is $O(N^3)$

Similar but simpler challenge is: LeetCode: Valid Parentheses.

Approach with stack

Stack could used to check whether a string is a valid parenthese, but how can we get the longest valid parenthese?

When we encounter a ‘(‘, we push the index of current character into the stack, and when we encounter a ‘)’ we pop a index from stack, if stack is empty, we use index - stack.top to get the length of substring.

The time complexity is: $O(N)$, and space complexity is $O(N)$.

#define max(a, b) ((a) > (b) ? (a) : (b))
class Solution {
public:
  int longestValidParentheses(string s) {
    stack<int> st;
    int ans = 0;
    st.push(-1);
    for(size_t i =0; i < s.size(); i++) {
      if(s[i] == '(')
        st.push(i);
      else {
        st.pop();
        if(st.empty())
          st.push(i);
        else
          ans = max(ans, i - st.top());
      }
    }
    return ans;
  }
};

Approach with Dynamic Programming

The key for dynamic programming is constructing a dp array for optimizing time performance.

Suppose dp[i] means the length of the longest valid substring ending at ith index. When loop over the characters in string, there are two scenarios:

1: s[i]=’)’ and s[i-1]=’(‘, string looks like “……()” =>

dp[i] = dp[i-2] + 2

2: s[i]=’)’ and s[i-1]=’)’, string looks like “((…..))” =>

One example of input is like (()()).

We need to test whether s[i-dp[i-1]-1] is a corresponding ‘(‘, if so we update the dp value:

int prev = (i-dp[i-1]-2 >= 0) ? (dp[i-dp[i-1]-2]) : 0;
dp[i] = dp[i-1] + 2 + prev;

class Solution {
public:
  int longestValidParentheses(string s) {
    if(s.size() < 2) return 0;
    vector<int> dp (s.length(), 0);
    for(int i = 1; i < s.length(); i++){
      if(s[i] == ')'){
        if(s[i-1] == '('){
          dp[i] = 2 + ((i-2 >= 0)? dp[i-2] : 0);
        }
        else{
          if (i-dp[i-1]-1 >= 0 && s[i-dp[i-1]-1] == '('){
            int prev = (i-dp[i-1]-2 >= 0) ? (dp[i-dp[i-1]-2]) : 0;
            dp[i] = dp[i-1] + 2 + prev;
          }
        }
      }
    }
    return *(max_element(dp.begin(), dp.end()));
  }
};

Approach without O(N) space

This is a very clever approach, time complexity is still $O(N)$, but space complexity is $O(1)$.

Use left and right to record the number of ‘(‘ and ‘)’, When iterate over string from left to right, update these two count, left+right is the number of current length of valid parentheses. Whenever right > left, set the counts to zero. Do the same thing with scanning from right to left.

#define max(a, b) ((a) > (b) ? (a) : (b))
class Solution {
public:
  int longestValidParentheses(string s) {
    int ans = 0, left = 0, right = 0;
    for(int i=0; i < s.size(); i++) {
      if(s[i] == '(')   left++;
      if(s[i] == ')')   right++;
      if(left == right) ans = max(ans, left+right);
      if(right > left)  left = right = 0;
    }

    left = right = 0;
    for(int i=s.size()-1; i >= 0; i--) {
      if(s[i] == '(')   left++;
      if(s[i] == ')')   right++;
      if(right == left) ans = max(ans, left+right);
      if(left > right)  left = right = 0;
    }
    return ans;
  }
};

Preparing for an interview? Check out this!