# Share my solution with o(n) time and constant space, which is better than DP or using stack.

• I think my solution is better than DP or stack because it uses constant space.

``````public int longestValidParentheses(String s) {
if (s == null)
return 0;
int max = 0, numOfLeftBracket = 0, tempMax = 0, tempStart = -1;
boolean isLast=false;
for (int i = 0; i <= s.length(); i++) {
char ch = i==s.length()?')':s.charAt(i);
isLast=i==s.length()?true:false;
if (ch == '(') {
if (tempStart == -1) {
tempStart = i;
}
numOfLeftBracket++;
continue;
}
if (numOfLeftBracket == 0||isLast) {
if (tempMax == 0)
continue;
/*now we have interval (tempStart, i), which "has" valid parentheses as tempMax, but need to be validated from tail to head by checking ")" */
int end = i==s.length()?s.length()-1:i;
int numofRightBrackets = 0, temMax2 = 0,temMax3=0;
while (end >= tempStart-1) {
char cha = end == tempStart-1?'(':s.charAt(end);
if (cha == ')') {
numofRightBrackets++;
} else {
if (numofRightBrackets == 0||end==tempStart-1){
temMax3=Math.max(temMax3,temMax2);
temMax2=0;
}else{
numofRightBrackets--;
temMax2++;
}
}
end--;
}
max = Math.max(max,temMax3);
tempMax = 0;
tempStart=-1;
} else {
tempMax++;
numOfLeftBracket--;
}

}
max = Math.max(max, tempMax);
return max * 2;
}``````

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