# Longest Valid Parentheses Problem Solution

Longest Valid Parentheses Problem: Given a string containing just the characters `'('` and `')'`, find the length of the longest valid (well-formed) parentheses substring.

Example :

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

Example :

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

## Problem Solution In Python

`````` class Solution:
def longestValidParentheses(self, s: str) -> int:
if len(s) <= 1:
return 0
stack = []
maxLen = 0
stack.append(-1)
for i in range(len(s)):
if s[i] == '(':
stack.append(i)
elif s[i] == ')':
if stack[-1] != -1 and s[stack[-1]] == '(':
stack.pop()
maxLen = max(i - stack[-1],maxLen)
else:
stack.append(i)

return maxLen
``````

## Problem Solution In Java

``````class Solution {
public int longestValidParentheses(String s) {
int ans = 0;
char l = '(';
char r = ')';
int i =0;
int j;
int[] save = new int[s.length()];

while (i<s.length()){
j = i;
Stack<Integer> st = new Stack<Integer>();
while(j<s.length()){
else{
if (st.isEmpty()) {
i = j+1;
break;
}
save[st.pop()] = 1;
save[j] = 1;
if (st.isEmpty()) {
i = j+1;
break;
}
}
if (j==s.length()-1) i=j+1;
j++;
}
}

i = 0;
while (i<s.length()){
if (save[i] != 1) {
i++;
continue;
}
j = i;
while (j<s.length() && save[j] == save[i]) {
j++;
}
if ((j-i)>ans) ans = (j-i);
i = j;
}

return ans;
}
}
``````

## Problem Solution In C++

``````int longestValidParentheses(string s) {
stack<int> list;
list.push(-1);
int maxa = 0;
for(int i=0; i< s.length(); ++i){
if(s[i] == '('){
list.push(i);
}
else{
list.pop();
if(list.empty())
list.push(i);
maxa = max(maxa, i - list.top());

}
}
return maxa;

}
``````

## Problem Solution In C

``````#define MAXN (32767)

int stck[MAXN],dp[MAXN];

int longestValidParentheses(char* s) {
int i, ans = 0, top = 0;

for(i = 0; s[i]; i++)
{
dp[i] = 0;
if(s[i] == '(')
stck[top++] = i;
else if(top)
{
int tmp = stck[--top];
dp[i] = i - tmp + 1 + (tmp?dp[tmp-1]:0);
ans = ans < dp[i]?dp[i]:ans;
}
}
return ans;
}``````