Longest Valid Parentheses


  • 0

    Click here to see the full article post


  • 0
    V

    For solution #4 should work with just one counter. Increment it on open, decrement on close, don't let it be negative, that's it.


  • 0

    Yes, you can do with one counter also. I thought two counters will make code more understandable.


  • 0
    N

    @vladich
    In that case, you need another variable to store the length


  • 0
    A
    This post is deleted!

  • 0

    @alexh95
    It is correct. Output of ")(" is 0. The condition if(right>left) right=left=0 will handle this example.


  • 0
    1

    did you find all the approach access the time limit?


  • 0
    M

    For #4 why do we need also do it from right to left?


  • 0

    @MitchellHe
    Consider the input "(()" , left to right scan will output 0, but the answer is 2.


  • 0
    H

    The dp approach maybe can simplify the IF condition of s[i-1] == '(' or ')'
    just consider the s[i-1] == '(' is a kind of situation that dp[i-dp[i-1]-2] + dp[i-1] + 2
    means that there is no Parenthese between '('(s[i-dp[i-1]-1]) and ')'(s[i])
    Python Solution

    class Solution(object):
        def longestValidParentheses(self, s):
            """
            :type s: str
            :rtype: int
            """
            n = len(s)
            dp = [0]*n
            ret = 0
            for i in range(n):
                if s[i] == ')':
                    if i - dp[i-1] > 0 and s[i-dp[i-1]-1] == '(':
                        dp[i] = (dp[i-dp[i-1]-2] if i - dp[i-1] > 1 else 0) + dp[i-1]+2
                        ret = max(ret, dp[i])
            return ret
         
    

  • 0
    M

    Excellent document. Yet I just tried #4 and got Time Limit Exceed.


  • 0

    @MitchellHe Try to submit again. It will get accepted.


  • 2

    For approach #4, the animation is wrong. In the left pass, when you reach index 1, the left/right counter should not be reset to 0.


  • 0

    @yangshun Thanks for pointing it out. I have corrected it. Thanks.


  • 0
    M

    It looks your Solution that uses stack times out.


  • 0

    @MitchellHe Try to submit it 3-4 times, you will definitely get AC.


  • 0
    S

    For approach #3, the code is right, but the last slide is wrong, 4 should be popped out first, so the answer is 7 - 3 = 4, maxlength is 4. Dummy head is a good idea.


  • 1
    S

    So I had hard time understanding "stack" approach. Thank you for sharing.

    For others who're also struggling to understand stack approach. Stack at any given point contains an index "after which valid substring could potentially start".
    So begins with -1 (optimistically valid substring could start with 0 index)
    Whenever "(" is encountered, assuming valid substring will begin after "(" (but excluding current "("'s position).
    Whenever ")" is encountered, top of stack is pooped - this takes care of immediately previous "(" but optimistic assumption of immediately previous's previous "("'s index came true. So length is current index - top of stock. "(" always assume that valid string will be "after" "(", ")" pop top of stack (if not empty) and find length of valid string found. If ")" is encountered with empty stack. Assume valid string will begin after ")".

    Cumulative pushing "(" (or ")" if stack is empty) takes care of extending substring with balanced parentheses.


  • 0
    I

    Damn, the feeling you get when your intuition solves the problem is ineffable..Solved using stack approach..Thought I wouldn't be able to solve it without looking at the solution..But after 1 day of thinking and wondering, finally solved it. :)


  • 0
    S

    the stack approach does not work for "(()()"
    it returns 2 where as expected 4


Log in to reply
 

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