Longest Valid Parentheses
Problem Description
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')'.
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
The simplest way to solve this problem is to generate all possible substrings and check each one to determine if it is a valid parentheses string. A valid parentheses string must have balanced opening and closing parentheses.
Methodology:
- Iterate over all possible substrings of the given string.
- For each substring, check if it is valid by ensuring that the count of '(' matches the count of ')'.
- Track the length of the longest valid substring found.
Code:
- Time Complexity: O(n^3), due to generating and checking each substring.
- Space Complexity: O(n), to store substrings temporarily.
2. Using a Stack
Intuition:
A stack can help keep track of indices of unmatched '(' characters. Whenever a valid pair is found, calculate the length of valid substrings till then using these indices from the stack.
Methodology:
- Use the stack to store the indices of '(' characters.
- When a ')' is encountered, pop from the stack; if the stack is empty, current valid substring length is zero, otherwise calculate the length from the new top of the stack.
- Maintain a max length of such valid substrings.
Code:
- Time Complexity: O(n), scan through the string once.
- Space Complexity: O(n), space used by the stack.
3. Optimized Two-Pass Counter
Intuition:
Instead of using a stack, two traversals maintaining counters (left and right) to track opening '(' and closing ')' parentheses can be more space-efficient.
Methodology:
- Traverse the string from left to right:
- Increment
leftcounter for '(' andrightcounter for ')'. - If both counters are equal, update the max length found.
- Reset counters if
rightbecomes greater thanleft.
- Traverse again from right to left:
- Use the same counters, but increment
rightfor ')' andleftfor '(' to ensure all cases are checked. - Reset counters if
leftbecomes greater thanright.
Code:
- Time Complexity: O(n) for scanning the string twice.
- Space Complexity: O(1), constant space usage.