32. Longest Valid Parentheses
Longest Valid Parentheses (LeetCode 32) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Stack Patterns pattern, in the Valid Parentheses Matching subpattern.
How to solve Longest Valid Parentheses
Longest Valid Parentheses is a Valid Parentheses problem, part of Stack Patterns. Master parentheses validation and balancing using stack. Handle multiple bracket types and minimum additions.
Work towards the solution in these steps:
- Consider using a stack to keep track of indices of characters as you traverse the string; this data structure can help you efficiently match parentheses.
- Push the index of the last unmatched ')' or a sentinel value onto the stack before processing to help calculate lengths of valid substrings.
- When you encounter '(', push its index onto the stack; when you encounter ')', pop from the stack and use the current index and the new top of the stack to determine the length of a valid substring.
The reference solution runs in O(n) time and O(1) space.
The Longest Valid Parentheses solution and editorial walks through the full approach with reference code.
Problem statement
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 104
- s[i] is '(', or ')'.
Topics and companies
Topics: String, Dynamic Programming, Stack.
Reported in interviews at Amazon, Facebook, Apple, ByteDance.
How to practise Longest Valid Parentheses on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open Longest Valid Parentheses in the code editor, or read the Longest Valid Parentheses editorial for a worked solution with its approach and complexity analysis.
Where Longest Valid Parentheses sits in the DSA pattern sheet
Problems related to Longest Valid Parentheses
Other problems that use the same Valid Parentheses Matching and Stack Patterns techniques:
- Minimum Add to Make Parentheses Valid — Medium, same subpattern
- Minimum Number of Swaps to Make the String Balanced — Medium, same subpattern
- Minimum Remove to Make Valid Parentheses — Medium, same subpattern
- Valid Parentheses — Easy, same subpattern
- Valid Parenthesis String — Medium, same subpattern
- Asteroid Collision — Medium, same pattern
Longest Valid Parentheses FAQ
What is the LeetCode number of Longest Valid Parentheses?
Longest Valid Parentheses is LeetCode problem 32, rated Hard.
What pattern is used to solve Longest Valid Parentheses?
Longest Valid Parentheses is a Valid Parentheses problem. It belongs to the Stack Patterns pattern, in the Valid Parentheses Matching subpattern.
What is the time complexity of Longest Valid Parentheses?
The reference solution runs in O(n) time and O(1) space.
Which companies ask Longest Valid Parentheses?
Longest Valid Parentheses has been reported in interviews at Amazon, Facebook, Apple, ByteDance.