LeetCode: Longest Valid Parentheses

\(\)

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)\).

2020_02_02_longest-valid-parentheses.org_20200202_221253.png

#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;

2020_02_02_longest-valid-parentheses.org_20200202_222648.png

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.

2020_02_02_longest-valid-parentheses.org_20200203_134647.png

#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!

Last Updated on

Leave a Reply

Your email address will not be published. Required fields are marked *