easy java O(n) solution without stack


  • 1
    R
    public class Solution {
        public int longestValidParentheses(String s) {
            if(s.length() == 0) return 0;
            // int[] dp = new int[s.length()];
            String reverse = new StringBuilder(s).reverse().toString();
            return Math.max(helper(s, new char[]{'(',')'}), helper(reverse, new char[]{')','('})); 
        }
        
        private int helper(String s, char[] param) {
            int ret = 0;
            int count = 0;
            int len = 0;
            for(int j = 0; j < s.length(); j++) {
                if(s.charAt(j) ==param[0]) {
                    count++;
                }else {
                    count--;
                }
                len++;
                if(count == 0) {
                    ret = Math.max(ret, len);
                }
                if(count == -1) {
                    count = 0;
                    len = 0;
                }
            }
            return ret;
        }
    }
    

Log in to reply
 

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