Python O(n) time, O(n) space solution with explanation


  • 0
    K

    Central idea is to be able to extend valid parentheses, like ()() notice that the second () extends the previous valid parenthesis to give a length of 4.

    Other examples:
    ()(() - in this case, longest valid is 2, but the moment we add another parentheses at the end ()(()), the whole string becomes a valid parentheses, so it is important to remember at i = 2 that there was a valid parentheses that ended just before it, so if a valid parentheses is created using i=2 as the starting point (opening parenthesis), the previous length can be added to it.

    For this, we can use an array (I call this array LengthEndingAtIndex as it stores the length of valid parenthesis ending at every offset. Whenever I find a valid parentheses (using a stack), I just store the current valid length into this array.

    Please let me know if any part is not clear, beginner here.

    
    class Solution(object):
        def longestValidParentheses(self, s):
            """
            :type s: str
            :rtype: int
            """
            stack = []
            maxLen = 0
            currentRun = 0
            
            LengthEndingAtIndex = [0 for i in range(0, len(s)+1)]
    
            for i in range(0, len(s)):
                if len(stack) == 0:
                    if s[i] == '(':
                        stack.append((i, s[i]))
                    continue
                
                topOfStackIndex, topOfStackParenthesis = stack[-1]
                
                if s[i] == ')':
                    if topOfStackParenthesis == '(':
                        stack = stack[0:-1]
                        currentRun = (i - topOfStackIndex + 1) + LengthEndingAtIndex[topOfStackIndex]
                        maxLen = max(currentRun, maxLen)
                        LengthEndingAtIndex[i+1] = currentRun
                    continue
                
                else:
                    stack.append((i, s[i]))
                
            return max(LengthEndingAtIndex)

Log in to reply
 

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