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 "()()".
Table of Contents
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()){
if (s.charAt(j) == l) st.add(j);
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;
}