Java O(n) solution with at most two passes, No Stack


  • 0

    For the first pass we scan the string from front. We exit the loop till we found more ')' than '(' or we reach the end.

    1. If at ith position we found more ')' than '(' for the first time, then 0 to i-1 substring is valid, we recursively search if there's longer one after i.
    2. else if we found same number of '(' and ')' by the end, the entire string is valid
    3. else if we found more '(' than ')' we can reverse the string and swap the role of '(' and ') now we can guarantee the reversed string fall into the first case.
        private int helper(String s, char[] p) {
            if (s.length() == 0) return 0;
            int lp = 0, i, start = 0;
            while (start < s.length() && s.charAt(start) == p[1]) start++;
            i = start;
            while (i < s.length() && lp >= 0) {
                if (s.charAt(i++) == p[0]) lp++;
                else lp--;
            }
            if (lp < 0) {
                return Math.max(i-start-1, helper(s.substring(i), p));
            } else if (lp == 0){
                return s.length()-start;
            } else return helper(new StringBuilder(s.substring(start)).reverse().toString(), new char[]{')', '('});
        }
        public int longestValidParentheses(String s) {
            return helper(s, new char[]{'(', ')'});
        }
    

Log in to reply
 

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