Simple JAVA solution, O(n) time, one stack


  • 111
    J
    public class Solution {
        public int longestValidParentheses(String s) {
            Stack<Integer> stack = new Stack<Integer>();
            int max=0;
            int left = -1;
            for(int j=0;j<s.length();j++){
                if(s.charAt(j)=='(') stack.push(j);            
                else {
                    if (stack.isEmpty()) left=j;
                    else{
                        stack.pop();
                        if(stack.isEmpty()) max=Math.max(max,j-left);
                        else max=Math.max(max,j-stack.peek());
                    }
                }
            }
            return max;
        }
    }
    

  • 4
    D

    truly brilliant to store the index into stack (instead of the parentheses)


  • 37
    E

    Nice solution! Inspired by your solution. I changed a little to make it shorter and easier.

    public class Solution {
        public int longestValidParentheses(String s) {
            LinkedList<Integer> stack = new LinkedList<>();
            int result = 0;
            stack.push(-1);
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == ')' && stack.size() > 1 && s.charAt(stack.peek()) == '(') {
                    stack.pop();
                    result = Math.max(result, i - stack.peek());
                } else {
                    stack.push(i);
                }
            }
            return result;
        }
    }
    

    The idea is simple, we only update the result (max) when we find a "pair".
    If we find a pair. We throw this pair away and see how big the gap is between current and previous invalid.
    EX: "( )( )"
    stack: -1, 0,
    when we get to index 1 ")", the peek is "(" so we pop it out and see what's before "(".
    In this example it's -1. So the gap is "current_index" - (-1) = 2.
    The idea only update the result (max) when we find a "pair" and push -1 to stack first covered all edge cases.


  • 0
    G

    when I use the Stack instead of LinkedList, I got TLE, can anyone help me figure out why LinkedList used as a stack is faster than Stack presentation.


  • 2
    S

    The cleanest code for this problem. Thanks. But why do I get a RTE if I replace stack.size() > 1 to !stack.empty() ??


  • 2
    Q

    @EdickCoding Thank you for your code. I tried removing pushing -1 at first and I got TLE error, any idea? My code is:

    public class Solution {
        public static int longestValidParentheses(String s) {
            Stack<Integer> stack = new Stack<>();
            int result = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == ')' && stack.size() > 0 && s.charAt(stack.peek()) == '(') {
                    stack.pop();
                    result = Math.max(result, stack.size() == 0 ? i + 1 : i - stack.peek());
                } else {
                    stack.push(i);
                }
            }
            return result;
        }
    }
    
    

    Thank you!


  • 0
    K

    @quincyhehe I believe it will miss the corner case in that way.


  • 0
    Q

    @kesai Thank you for your reply. But why does it fail the test case "(((((((((((((((((((" ? I've tried running locally and it was fine. Thanks.


  • 0
    L

    @quincyhehe I met the same problem, the system should has updated the test cases, and the DP method maybe help


  • 0
    Q

    @liujunhongznn

    Thank you! So you mean right now it can pass the OJ now?


  • 0
    Q
    This post is deleted!

  • 1

    @EdickCoding Amazing! Very clear explanation! You saved me!
    I didn't notice that it ends up with TLE.
    Deque is much faster than Stack, since it's un-synchronized (Stack extends Vector). Now it works!


  • 0

    Actually i dont think your code is O(n)time. you ignore the time cost on stack calculate


  • 0
    This post is deleted!

  • 0
    R

    nice solution
    this is mine:

    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;
        }
    }
    

  • 0
    R

    Just awesome.


  • 0
    G

    @EdickCoding said in Simple JAVA solution, O(n) time, one stack:

    s.charAt(stack.peek()) == '('

    You have only numbers in the stack and not parenthesis


  • 0
    C

    Is this solution actually DP? Using stack this solution just calculates the length of valid sequences and return the max length. I don't understand the DP subproblem in this solution.


  • 2
    E

    @gogoflg2016 @quincyhehe Try using ArrayDeque instead of Stack and specify the initial capacity like this:
    Deque<Integer> stack = new ArrayDeque<>(s.length());

    Stack and ArrayDeque are implemented with resizable array, and every time it is full, all of the elements will be copied to a new allocated array, which is costly if this process is invoked repeatedly and thus leads to TLE on large test cases. Specifying an initial capacity can prevent this from happening.


  • 0
    R

    Javascript version:

    var longestValidParentheses = function(s) {
        var stk = []
        var mx = 0
        var left = -1
        for(var j = 0; j < s.length; j++) {
            if(s[j] == '(') stk.push(j)
            else {
                if (stk.length == 0) left = j
                else {
                    stk.pop()
                    if(stk.length == 0) mx = Math.max(mx, j - left)
                    else mx = Math.max(mx, j - stk[stk.length - 1])
                }
            }
        }
        return mx;
    };
    

Log in to reply
 

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