32 Longest Valid Parentheses

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        """
        note that every index in stack is offset to the left by one,
        to make finding the length between two indices easier.
        (normally you'd have to do r - l + 1, but in our case, l is already l-1).
        """
        # we initialize with -1 for the case where the
        # valid substring starts at the beginning of s
        stack = [-1]
        ans = 0
 
        # stack stores the index BEFORE where
        # a valid substring could start
 
        for i in range(len(s)):
            if s[i] == "(":
                stack.append(i)
            else:
                stack.pop()
                if not stack:
                    stack.append(i)
                else:
                    ans = max(ans, i - stack[-1])
        return ans

Video walkthrough.

• 01:15 intuition of using a stack for these 20-valid-parentheses type problems.
• 02:14 intuition of storing the index numbers of the open parentheses in the string.
• 05:50 second solution.

table without id file.inlinks as Backlinks
where file.name = this.file.name

Related.

• 20-valid-parentheses.

References.

Categories:: stack, string