# Leetcode 32 Solution

https://leetcode.com/problems/longest-valid-parentheses

## Thinking Process

The most straightfowrad solution is to find out all the substrings, and then check each of them to see if they are well-formed parenthesis. If `N` is the size of the string, the time complexity is `O(N^3)`.

Given that the scale of the question is `3 * 10^4`, it is unlikely that we can pass if we are not `O(N)`. So let’s see if we can do it within `O(N)` or `O(N * lg N)`.

Let’s assume that `F(i)` means the longest well-formed parenthesis ending at position `i`.

First of all, `F(0) = 0`.

For any position after `0`, we can break down the string into this:

```s = ... x x x x x x x x x x x x x s[i] . . .```

For `F(i)`, therer are two cases:

• If the orange character is `(` and `s[i] == ')'`, it means from the substring from the orange character to `s[i]` is a well-formed parenthesis, because we know the green part before `s[i]` is a well-formed parenthesis. To make it even longer, we can add up the well-formed parenthesis before the orange character, i.e., the red part. In other words, `F(i) = 2 + F(i - 1) + F(i - F(i - 1) - 2)`.
• Otherwise, if the orange character is not `(` or `s[i] != ')'`, it means there is no well-formed parenthesis ending at position `i`. In this case, `F(i) = 0`.

The above algorithm can help us calculate each `F(i)` in `O(1)` time. So we just need to calculate all the `F(i)`s, and then return the maximum one.

## Time & Space Complexity

Assuming `N` is the size of the string:

• Time complexity: `O(N)`
• Space complexity: `O(N)`

## Solution

``````class Solution {
public:
int longestValidParentheses(string s) {
vector<int> dp(s.size());

int max_len = 0;

for (int i = 1; i < s.size(); i++)
{
int l = i - 1 - dp[i - 1];

if (s[i] == ')' && s[l] == '(')
{
dp[i] = dp[i - 1] + 2;
if (l > 0)
dp[i] += dp[l - 1];
}

max_len = max(max_len, dp[i]);
}

return max_len;
}
};
``````