Coder's Cat

LeetCode: Longest Valid Parentheses

2020-02-02

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

file:img/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;

file:img/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.

file:img/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!