Solution of O(n) time and O(1) Space


  • 1
    S

    The idea is simple, divide the String s into many segments. In each segment, the number of left parenthesis is always no less than the number of right parenthesis when counting from the start of each segment, for example, if we have a String s: "()(()))(()", it will be divided into two segments "()(())" and "(()". And for each segment, we will iterate from right to left, when the number of left parenthesis and right parenthesis are equal, we get a valid one, return the maximum of them.

    private int alwaysMoreOpen(int start, int end, String s){
        // return the length of longest valid parentheses when the num of left paranthesis is always more 
        int diff=0, temp=0, res=0;
        for(int i=end; i>start;i--){
            if(s.charAt(i)==')') diff++;
            else {
                if(diff>0){
                    diff--;
                    temp+=2;
                }
                else{
                    res=Math.max(temp,res);
                    temp=0;
                }
            }
        }
        return Math.max(temp,res);
    }
    
    public int longestValidParentheses(String s) {
        int start=-1,end=0, diff=0, res=0;
        while(end<s.length()){
            if(s.charAt(end)=='(') diff++;
            else{
                if(diff==0) {
                    // the boundary that the number of right parenthesis is more
                    res=Math.max(res,alwaysMoreOpen(start,end-1,s));
                    start=end;
                }
                else diff--;
            }
            end++;
        }
        return Math.max(res,alwaysMoreOpen(start,end-1,s));
    }

Log in to reply
 

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