wayetan
1/6/2014 - 10:03 AM

## Longest Valid Parentheses

Longest Valid Parentheses

``````/**
* 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.
*/

public class Solution {
public int longestValidParentheses(String s) {
int maxLen = 0, startFrom = -1;
Stack<Integer> lefts = new Stack<Integer>();
for(int i = 0; i < s.length(); i++){
// if it is open
if(s.charAt(i) == '(')
lefts.push(i);
else{
if(lefts.isEmpty()){
// no matching
startFrom = i;
}else{
// find a matching pair;
lefts.pop();
if(lefts.isEmpty()){
maxLen = Math.max(maxLen, i - startFrom);
}else{
maxLen = Math.max(maxLen, i - lefts.peek());
}
}
}
}
return maxLen;
}

// DP solution
public int longestValidParentheses(String s) {
if (s == null || "".equals(s)) return 0;
int[] dp = new int[s.length() + 1];
int max = 0;
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == ')' && i - dp[i] >= 1 && s.charAt(i - dp[i] - 1) == '(') {
dp[i + 1] = dp[i - dp[i] - 1] + dp[i] + 2;
}
}
for (int i = 0; i < dp.length; i++) {
if (dp[i] > max) max = dp[i];
}
return max;
}
}``````