Problem_32. Longest Valid Parentheses - xwu36/LeetCode GitHub Wiki
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4. code:
class Solution {
public int longestValidParentheses(String s) {
int n = s.length();
if(n == 0)
return 0;
int[] dp = new int[n];
Stack<Integer> stack = new Stack<Integer>();
int top, l, r;
for(int i = 0; i < n; i++){
if(s.charAt(i) == '(')
stack.push(i);
else if(!stack.isEmpty()){
top = stack.pop();
l = top - 1 >= 0 ? dp[top - 1] : 0;
r = dp[i - 1];
dp[i] = l + r + 1;
}
}
int maxLen = 0;
for(int num : dp)
maxLen = Math.max(maxLen, num);
return 2 * maxLen;
}
}