My O(n) solution using a stack


  • 288
    C
    class Solution {
    public:
        int longestValidParentheses(string s) {
            int n = s.length(), longest = 0;
            stack<int> st;
            for (int i = 0; i < n; i++) {
                if (s[i] == '(') st.push(i);
                else {
                    if (!st.empty()) {
                        if (s[st.top()] == '(') st.pop();
                        else st.push(i);
                    }
                    else st.push(i);
                }
            }
            if (st.empty()) longest = n;
            else {
                int a = n, b = 0;
                while (!st.empty()) {
                    b = st.top(); st.pop();
                    longest = max(longest, a-b-1);
                    a = b;
                }
                longest = max(longest, a);
            }
            return longest;
        }
    };
    

    The workflow of the solution is as below.

    1. Scan the string from beginning to end.
    2. If current character is '(',
      push its index to the stack. If current character is ')' and the
      character at the index of the top of stack is '(', we just find a
      matching pair so pop from the stack. Otherwise, we push the index of
      ')' to the stack.
    3. After the scan is done, the stack will only
      contain the indices of characters which cannot be matched. Then
      let's use the opposite side - substring between adjacent indices
      should be valid parentheses.
    4. If the stack is empty, the whole input
      string is valid. Otherwise, we can scan the stack to get longest
      valid substring as described in step 3.

  • 0
    R
    This post is deleted!

  • 1
    N

    Your explanation is awsome !!


  • 0
    W

    Thanks! This is awesome!


  • 73
    D

    This is my DP solution, just one pass

    V[i] represents number of valid parentheses matches from S[j to i] (j<i)

    V[i] = V[i-1] + 2 + previous matches V[i- (V[i-1] + 2) ] if S[i] = ')' and '(' count > 0

    public int longestValidParentheses(String s) {
        char[] S = s.toCharArray();
        int[] V = new int[S.length];
        int open = 0;
        int max = 0;
        for (int i=0; i<S.length; i++) {
            if (S[i] == '(') open++;
            if (S[i] == ')' && open > 0) {
                // matches found
                V[i] = 2+ V[i-1];
                // add matches from previous
                if(i-V[i]>0)
                    V[i] += V[i-V[i]];
                open--;
            }
            if (V[i] > max) max = V[i];
        }
        return max;
    }

  • 0
    M

    Great solution. Only one small question: Do we need if(i-V[i]>0) ? I mean, i - V[i] should be always non negative and V[0] is always 0. Hence, do we need the if condition ?


  • 0
    H

    Consider the case "((()))". When i == 5, V[i] is 6. i - V[i] won't always be non-negative.


  • 2

    "substring between adjacent indices should be valid parentheses." --- Great observations!


  • 0
    H

    That is the best one answer.


  • 0
    W

    awesome!!!!!!!!!!!!!!


  • 0
    A

    really smart!


  • 20

    Thanks for your answer. In fact, we don't have to get the maximum length after the first scan. Instead, we can get it dynamically while push and pop, which makes the run time get better. Following is my code.

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

    }


  • 0
    B

    This is absolutely the best answer for this problem!


  • 0
    H
    This post is deleted!

  • 7
    H

    Thank you for your cool answer. I get a one-pass answer based on your answer.


    int longestValidParentheses(string s) {
        int size = s.size(), res = 0;
        if(size < 2) return res;
        stack<int> si;
        for(int i = 0; i < size; ++i) {
            if('(' == s[i]) si.push(i);
            else {
                if(si.empty()) si.push(i);
                else {
                    if(s[si.top()] == '(') {
                        si.pop();
                        res = max(i - (si.empty()? -1: si.top()), res);
                    }
                    else si.push(i);
                }
            }
        }
        return res;
    }
    

  • 0
    W

    Great!!!!!!!


  • 0
    J

    good job!!!!.


  • 3
    T

    python version:

        def longestValidParentheses(self, s):
             stack, res, s = [0], 0, ')'+s
             for i in xrange(1, len(s)):
                 if s[i] == ')' and s[stack[-1]] == '(':
                     stack.pop()
                     res = max(res, i - stack[-1])
                 else:
                     stack.append(i)
             return res

  • 0
    V

    Thanks for sharing,nice explanation.


  • 0

    Upvoting cuz - you were practicing on the New Year's Eve too! :D


Log in to reply
 

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