public class Solution {
public int longestValidParentheses(String s) {
Stack<Integer> stack = new Stack<Integer>();
int max=0;
int left = -1;
for(int j=0;j<s.length();j++){
if(s.charAt(j)=='(') stack.push(j);
else {
if (stack.isEmpty()) left=j;
else{
stack.pop();
if(stack.isEmpty()) max=Math.max(max,j-left);
else max=Math.max(max,j-stack.peek());
}
}
}
return max;
}
}
public class Solution {
public int longestValidParentheses(String s) {
int maxans = 0;
int dp[] = new int[s.length()];
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == ')') {
if (s.charAt(i - 1) == '(') {
dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
} else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
}
maxans = Math.max(maxans, dp[i]);
}
}
return maxans;
}
}
public class Solution {
public int longestValidParentheses(String s) {
char[] S = s.toCharArray();
int [] DP = new int [S.length];
int max = 0;
for (int i=1; i< S.length; i++) {
if (S[i] == ')') {
int j=i-1-DP[i-1];
if (j>=0 && S[j] == '(') {
DP[i] = 2+DP[i-1]+(j>0? DP[j-1]:0);
}
}
max = Math.max(max, DP[i]);
}
return max;
}
}
public class Solution {
public int longestValidParentheses(String s) {
if (s == null || s.length() < 2) return 0;
Deque<Integer> stack = new ArrayDeque<>();
//Stack<Integer> stack = new Stack<Integer>();
int res = 0;
stack.push(-1);
for (int i = 0; i < s.length(); i++) {
//char cur = s.charAt(i); TLE
if (s.charAt(i) == '(') {
stack.push(i);
} else {
stack.pop();
if (stack.isEmpty()) {
stack.push(i);
} else {
res = Math.max(res, i - stack.peek());
}
}
}
return res;
}
}