Explaining solution using Stack


  • 16
    N

    I have seen a lot of good answers but it is not immediately clear how they are achieving the result. I am going to make an attempt to explain my solution using a stack. Every time we encounter '(' we push the index onto the stack and when we encounter ')' we pop the stack and use the current index minus the index at the top of the stack to be the current_length. we check against the max found so far and update if needed. Here is the code

    public static int longestValidParentheses(String s) {
    
    
            Stack<Integer> bracketStack = new Stack<Integer>();
            int max_len=0;
            int current_len=0;
            int last = -1;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') {
                    
                        bracketStack.push(i);
                }
                else{
    
                    if(!bracketStack.isEmpty())
                    {
                        bracketStack.pop();
    
                    if(!bracketStack.isEmpty())
                        current_len = i-bracketStack.peek();
                    else
                        current_len=i-last;
                    max_len = Math.max(max_len,current_len);
                    }
                    else{
                        
                        last = i;
                    }
                }
    
            }
    
    
            return max_len;
        }

  • 9
    P

    I modified your solution, so it's more concise!

    int longestValidParentheses(string s) {
        stack<int> st;
        int len, maxLen = 0;
        st.push(-1);
        for (int i = 0;i < s.size();++i)
            if (s[i] == '(')
                st.push(i);
            else {
                st.pop();
                if (!st.empty()) {
                    len = i - st.top();
                    maxLen = max(maxLen, len);
                } else
                    st.push(i);
            }
        return maxLen;
    }

  • 0
    H

    Nice try! good job :)


  • 0
    S

    Nice use of boundary index!


  • 0
    A

    @phu1ku hey can you please tell me how it will return 4 for ()() this input,

    its returning 1 for me, I debugged code as well.
    i-st.top() to get the curr len, how this is working, would appreciate if you can explain.

    e.g - for below input -
    ()
    i-st.top()
    1-0 = will return 1;

    ()()
    i-st.top()
    3-2= will return 1 as well,

    where I am making the mistake.


  • 0
    A

    @phu1ku Ah!! silly me, was using wrong stack method, I got it how it is working. Thanks though..


Log in to reply
 

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