Java solution, probably overkill


  • 0
    W

    The key idea is to have a "pre" tracking the valid length of parens right before an OpenParen. Mark each open paren with its index and compute at the close paren the distance from it's matching paren.

    It could be simplified further, but the idea is the same.

    import java.util.ArrayDeque;
    import java.util.Deque;
    
    class Solution {
        static class OpenParen {
            char c;
            int index;
            int pre; // preceding valid len.
            OpenParen(char c, int index, int pre){
                this.c = c;
                this.index = index;
                this.pre = pre;
            }
            int compute_valid_len(int close_idx) {
                return pre + close_idx - index + 1;
            }
        }
        private boolean is_left(char c) {
            return c == '(';
        }
    
        public int longestValidParentheses(String s) {
            char[] a = s.toCharArray();
            int max_len = 0;
            int pre = 0;
            Deque<OpenParen> st = new ArrayDeque<>();
            for (int i=0;i<a.length;i++) {
                if (is_left(a[i])){
                    st.push(new OpenParen(a[i], i, pre));
                    pre = 0;
                } else { // right paren.
                    if (st.isEmpty()) {
                        pre = 0;
                    } else {
                      if (is_left( st.peek().c )) { // close with right.
                          int dist = st.peek().compute_valid_len(i);
                          max_len = Math.max(dist, max_len);
                          pre = dist;
                          st.pop();
                      } else {
                          // right  paren never pushed.
                      }
                    }
                }
            }
    
    
            return max_len;
        }
    }
    

Log in to reply
 

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