Challenge Description
https://leetcode.com/problems/longestvalidparentheses/
Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (wellformed) parentheses substring.
Example 1:

Example 2:

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

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[i1]=’(‘, string looks like “……()” =>

2: s[i]=’)’ and s[i1]=’)’, string looks like “((…..))” =>
One example of input is like (()())
.
We need to test whether s[idp[i1]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)$.
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.
