# O(N)-time O(1)-space Java solution

• public class Solution {
public int longestValidParentheses(String s) {
int l = s.length();
int[] d = new int[l];
for(int i=0; i<l; i++)// +1 and -1 are more convinient, but it's possible to use the original string
d[i] = s.charAt(i)=='(' ? 1 : -1;
int b=0, e=l-1;// begin and end of the unsearched interval
int max=0;// result
int count=0; //nestling counter
left://find all valid substrings from the left side
while (b<e){
while(b<=e && d[b]==-1)//remove left ')'
b++;
count=0;
for(int c=b; c<=e; c++){
count+=d[c];
if(count==-1){//we found a valid substring
if(max<c-b)
max=c-b;
b=c;
continue left;
}
}
if(count==0)// all remainder was valid
return Math.max(max, e-b+1);
break;// counter>0 in the end, it means that valid substring should be searched from the right
}
right://find all valid substrings from the right side
while (b<e){
while(b<=e && d[e]==1)//remove right '('
e--;
count=0;
for(int c=e; c>=b; c--){
count+=d[c];
if(count==1){//we found a valid substring
if(max<e-c)
max=e-c;
e=c;
continue right;
}
}
return Math.max(max, e-b+1);//counter==0, in another case we would have found this substring on the left cycle
}
return max;
}
}

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