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


  • 0
    G
    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;
        }
    }
    

Log in to reply
 

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