Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.
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)$.
Approach with Dynamic Programming
The key for
dynamic programming is constructing a dp array for optimizing time performance.
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 “……()” =>
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:
Approach without O(N) space
This is a very clever approach, time complexity is still $O(N)$, but space complexity is $O(1)$.
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.
Preparing for an interview? Check out this!