```
public class Solution {
public int longestValidParentheses(String s) {
return ltr(s, 0, s.length());
}
public int ltr(String s, int start, int end) {
int left = start;
int openLeft = 0;
int max = 0;
for(int i = start; i < end; i++) {
if(s.charAt(i) == '(')
openLeft++;
else
openLeft--;
if(openLeft < 0) {
int length = i - left;
if(length > max)
max = length;
left = i + 1;
openLeft = 0;
}
}
if(openLeft == 0) {
int length = end - left;
if(length > max)
max = length;
} {
int length = rtl(s, left, end);
if(length > max)
max = length;
}
return max;
}
public int rtl(String s, int start, int end) {
int right = end;
int openRight = 0;
int max = 0;
for(int i = end - 1; i >= start; i--) {
if(s.charAt(i) == ')')
openRight++;
else
openRight--;
if(openRight < 0) {
int length = right - (i + 1);
if(length > max)
max = length;
right = i;
openRight = 0;
}
}
if(openRight == 0) {
int length = right - start;
if(length > max)
max = length;
}
return max;
}
}
```

I am pretty sure the code can be shorten to maybe half of the current size...... but why bother...

The idea is very simple, 2 iteration at most. First time from left to right, second time from right to left.

The second iteration is only needed if the first iteration has ends with unclosed left bracket.