How hard is LeetCode 32. Longest Valid Parentheses?

LeetCode 32. Longest Valid Parentheses is rated Hard on LeetCode.

What is the time complexity of LeetCode 32. Longest Valid Parentheses?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 32. Longest Valid Parentheses?

The Python solution on this page uses O(n), where n is the length of the string auxiliary space.

What topics does LeetCode 32. Longest Valid Parentheses cover?

LeetCode 32. Longest Valid Parentheses is tagged Stack, String and Dynamic Programming on LeetCode.

Longest Valid Parentheses — LeetCode 32 Python Solution

HardStackStringDynamic Programming

Problem: #32
Pattern: Stack
Reading time: 2 min
Source: leetcode.com

The problem

Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.

Example

Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Python solution

Python

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)
        f = [0] * (n + 1)
        for i, c in enumerate(s, 1):
            if c == ")":
                if i > 1 and s[i - 2] == "(":
                    f[i] = f[i - 2] + 2
                else:
                    j = i - f[i - 1] - 1
                    if j and s[j - 1] == "(":
                        f[i] = f[i - 1] + 2 + f[j - 1]
        return max(f)

Complexity

Measure	Complexity
Time	O(n)
Space	O(n), where n is the length of the string auxiliary

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 32. Longest Valid Parentheses is filed here because LeetCode tags it Stack, which is the vocabulary this hub collects.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 32. Longest Valid Parentheses?: LeetCode 32. Longest Valid Parentheses is rated Hard on LeetCode.
What is the time complexity of LeetCode 32. Longest Valid Parentheses?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 32. Longest Valid Parentheses?: The Python solution on this page uses O(n), where n is the length of the string auxiliary space.
What topics does LeetCode 32. Longest Valid Parentheses cover?: LeetCode 32. Longest Valid Parentheses is tagged Stack, String and Dynamic Programming on LeetCode.