# My 4ms Java Solution with double stack

• ``````public class Solution {
public int longestValidParentheses(String s) {
if(s==null || s.length()==0){
return 0;
}
int cnt;
int[] indexStack = new int[ s.length() ];
int[] bracketStack = new int[ s.length() ];
int isPtr, bsPtr;
int curUpper, curLower, maxUpper, maxLower, maxLen;

for(isPtr = bsPtr = -1, cnt = 0; cnt < s.length(); cnt++){
if(s.charAt(cnt) == '('){
indexStack[ ++isPtr ] = cnt;
} else if(isPtr > -1) {
bracketStack[ ++bsPtr ] = indexStack[ isPtr-- ];
bracketStack[ ++bsPtr ] = cnt;
}
}

if(bsPtr == -1){
return 0;
}
maxUpper = bracketStack[ bsPtr-- ];
maxLower = bracketStack[ bsPtr-- ];
maxLen = 2;
while(bsPtr > -1){
curUpper = bracketStack[ bsPtr-- ];
curLower = bracketStack[ bsPtr-- ];
if(curUpper == maxLower-1){
maxLower = curLower;
} else if(curUpper < maxLower-1) {
maxLen = Math.max(maxLen, maxUpper-maxLower+1);
maxUpper = curUpper;
maxLower = curLower;
}
}

return Math.max(maxUpper-maxLower+1, maxLen);
}
}
``````

In the first pass, I push the start and the end of every pair of parenthesis into bracketStack. So, every time I pop out a new pair from the bracketStack, if it's incorporated in the previous parenthesis, the maximum length remains unchanged. If its upper bound is only 1 less than then lower bound of the previous parenthesis, then these two are concatenated into a longer substring. If its upper bound is less than the lower bound of the previous parenthesis by more than one, then it's a new substring, and I'll need to save the current maximum length.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.