Is Longest Valid Parentheses easy or hard?

Longest Valid Parentheses is classified as a Hard problem on LeetCode. The challenge comes from correctly handling nested and overlapping parentheses while maintaining linear time complexity. Mastery usually requires familiarity with stack-based parsing or dynamic programming patterns.

Longest Valid Parentheses Python/Java solution

Python and Java implementations typically use a stack storing indices with an initial value of -1. Each time a closing parenthesis is processed, the stack is popped and the current valid length is calculated using the difference between the current index and the new stack top. This produces an O(n) solution.

How to solve Longest Valid Parentheses in O(n)?

Use either a stack or dynamic programming. The stack method stores indices of unmatched parentheses and calculates valid substring lengths using index differences as you scan the string. The dynamic programming method keeps a dp array where dp[i] represents the longest valid substring ending at index i.

What is the best approach for Longest Valid Parentheses?

The stack-based approach is widely considered the best interview solution. It scans the string once while storing indices of unmatched parentheses and computing valid lengths using index differences. This achieves O(n) time complexity with O(n) space and is easy to reason about during interviews.

Is Longest Valid Parentheses asked at Google/Amazon/Meta?

Longest Valid Parentheses appears in interview preparation lists for companies such as Google, Amazon, and Meta because it tests stack usage, string parsing, and dynamic programming reasoning. Variations of parentheses validation and longest valid substring problems are common in technical interviews.

What data structure is used in Longest Valid Parentheses?

The most common data structure used is a stack that stores indices of parentheses. It helps track boundaries of unmatched characters and calculate valid substring lengths efficiently. Dynamic programming is another technique used to build valid substring lengths incrementally.

What is the time complexity of Longest Valid Parentheses?

The optimal algorithms run in O(n) time where n is the length of the string. Both the stack approach and the dynamic programming solution process each character once. Brute force solutions are much slower at O(n^3) because they evaluate every substring.

Description Solution Video 12:51

32. Longest Valid Parentheses

Hard41.2% acceptance25 companies

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

Example 1:

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

Example 2:

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

Example 3:

Input: s = ""
Output: 0

Constraints:

0 <= s.length <= 3 * 10⁴
s[i] is '(', or ')'.

Asked at top 20 of 25 companies

Nike Maq Software Nykaa MakeMyTrip Roku Inmobi Meta

IBM Zoho Visa Sprinklr Booking.com

+8 more

Amazon Microsoft Tiktok Intuit Morgan Stanley

Google Bloomberg Uber

Topics

12:51

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution

32. Longest Valid Parentheses

Asked at top 20 of 25 companies

Topics

Similar problems