Java solution, two pointers


  • 1
    D
    public class Solution {
        public int longestValidParentheses(String s) {
            if(s == null || s.length() < 2)
                return 0;
            
            int len = s.length();
            int left = 0;
            int right = len - 1;
            
            while(left < right && s.charAt(left) == ')' && s.charAt(right) == '('){
                left++;
                right--;
            }
            
            s = s.substring(left, right + 1);
            if(s == null || s.length() < 2)
                return 0;
            
            len = s.length();
            int start = 0;
            int end = 0;
            int count = 0;
            int res = 0;
            
            while(end < len){
                
                while(end < len && count >= 0){
                    if(s.charAt(end) == '('){
                        count++;
                    }
                    else{
                        count--;
                    }
                    
                    if(count == 0){
                        res = Math.max(res, end - start + 1);
                    }
                    
                    end++;
                }
                
                if(count >= 0)
                    break;
                /*
                if((end - start - 1) % 2 == 0)
                    res = Math.max(res, end - start - 1);
                */
                
                start = end;
                count = 0;
                
            }
            
            if(count == 0)
                res = Math.max(res, end - start);
                
            start = len - 1;
            end = len - 1;
            count = 0;
            int res2 = 0;
            
            
            while(start >= 0){
                
                while(start >= 0 && count >= 0){
                    if(s.charAt(start) == '('){
                        count--;
                    }
                    else{
                        count++;
                    }
                    
                    if(count == 0){
                        res2 = Math.max(res2, end - start + 1);
                    }
                    
                    start--;
                }
                
                if(count >= 0)
                    break;
                /*
                if((end - start - 1) % 2 == 0)
                    res2 = Math.max(res2, end - start - 1);
                */
                    
                
                end = start;
                count = 0;
                
            }
            
            if(count == 0)
                res2 = Math.max(res2, end - start);
            
            
            if(res == 0 && res2 != 0)
                return res2;
            else if(res != 0 && res2 == 0)
                return res;
            else if(res != 0 && res2 != 0)
                return Math.max(res, res2);
            
            return 0;
            
        }
    }
    

Log in to reply
 

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