## Algorithm

Problem Name: 32. Longest Valid Parentheses

Given a string containing just the characters `'('` and `')'`, return the length of the longest valid (well-formed) parentheses

Example 1:

```Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".
```

Example 2:

```Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".
```

Example 3:

```Input: s = ""
Output: 0
```

Constraints:

• `0 <= s.length <= 3 * 104`
• `s[i]` is `'('`, or `')'`.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
int longestValidParentheses(char* s) {
int i, l, n, *v;
int max;

if (!s) return 0;

l = strlen(s);
v = malloc(l * sizeof(int));
//assert(v);

n = 0;
for (i = 0; i < l; i ++) {
if (s[i] == '(') {
v[i] = 1;
n ++;
} else /*if (s[i] == ')')*/ {
if (n > 0) {
n --;
v[i] = 1;
} else {
v[i] = 0;
}
}
}

n = 0;
for (i = l - 1; i >= 0; i --) {
if (s[i] == ')') {
if (v[i]) {
n ++;
}
} else /*if (s[i] == '(')*/ {
if (n > 0) {
n --;
} else {
v[i] = 0;
}
}
}

n = 0; max = 0;
for (i = 1; i < l; i ++) {
if (v[i]) {
v[i] = v[i - 1] + 1;

if (max < v[i]) {
max = v[i];
}
}
}

free(v);

return max;
}
``````
Copy The Code &

Input

cmd
s = "(()"

Output

cmd
2

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int longestValidParentheses(String s) {
int maxLength = 0;
int leftIdx = 0;
int rightIdx = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
leftIdx++;
} else {
rightIdx++;
}
if (leftIdx == rightIdx) {
maxLength = Math.max(maxLength, 2 * rightIdx);
} else if (rightIdx > leftIdx) {
leftIdx = rightIdx = 0;
}
}
leftIdx = 0;
rightIdx = 0;
for (int i = s.length() - 1; i >= 0; i--) {
if (s.charAt(i) == '(') {
leftIdx++;
} else {
rightIdx++;
}
if (leftIdx == rightIdx) {
maxLength = Math.max(maxLength, 2 * rightIdx);
} else if (leftIdx > rightIdx) {
leftIdx = rightIdx = 0;
}
}
return maxLength;
}
}
``````
Copy The Code &

Input

cmd
s = ")()())"

Output

cmd
4

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const longestValidParentheses = function(s) {
const arr = s.split("")
const dp = new Array(arr.length).fill(0)
let open = 0
let max = 0
for (let i = 0; i < arr.length; i++) {
if (arr[i] === "(") open++
if (arr[i] === ")" && open > 0) {
dp[i] = 2 + dp[i - 1]
if (i - dp[i] > 0) dp[i] += dp[i - dp[i]]
open--
}
if (dp[i] > max) max = dp[i]
}
return max
}
``````
Copy The Code &

Input

cmd
s = ""

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def longestValidParentheses(self, s):
stack, mx = [], 0
for i, c in enumerate(s):
if c == ")" and stack and s[stack[-1]] == "(": stack.pop()
else: stack.append(i)
stack = [-1] + stack + [len(s)]
for i1, i2 in zip(stack, stack[1:]): mx = max(mx, i2 - i1 - 1)
return mx if len(stack) > 2 else len(s)
``````
Copy The Code &

Input

cmd
s = "(()"

Output

cmd
2

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _032_LongestValidParentheses
{
public int LongestValidParentheses(string s)
{
int i, maxLen = 0, lastError = -1, depth = 0;

for (i = 0; i < s.Length; i++)
{
if (s[i] == '(') { depth++; }
else
{
depth--;
if (depth < 0)
{
depth = 0;
lastError = i;
}
else if (depth == 0)
{
maxLen = maxLen < i - lastError ? i - lastError : maxLen;
}
}
}

lastError = s.Length;
depth = 0;
for (i = s.Length - 1; i >= 0; i--)
{
if (s[i] == ')') { depth++; }
else
{
depth--;
if (depth < 0)
{
depth = 0;
lastError = i;
}
else if (depth == 0)
{
maxLen = maxLen < lastError - i ? lastError - i : maxLen;
}
}
}

return maxLen;
}
}
}
``````
Copy The Code &

Input

cmd
s = ")()())"

Output

cmd
4