Stack
Longest Valid Parentheses
hard
Count: 10
DESCRIPTION (inspired by Leetcode.com)
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring. A well-formed parentheses string is one that follows these rules:
- Open brackets must be closed by a matching pair in the correct order.
For example, given the string "(()", the longest valid parentheses substring is "()", which has a length of 2. Another example is the string ")()())", where the longest valid parentheses substring is "()()", which has a length of 4.
Example 1:
Inputs:
s = "())))"
Output:
2
(Explanation: The longest valid parentheses substring is "()")
Example 2:
Inputs:
s = "((()()())"
Output:
8
(Explanation: The longest valid parentheses substring is "(()()())" with a length of 8)
Example 3:
Inputs:
s = ""
Output:
0
Explanation
At a high level, we can solve this problem by iterating over each index of the string, and then calculating the length of the longest valid parentheses substring that ends at that index. We can then take the maximum of these lengths to get the final answer.
Each time we encounter a closing parenthesis ')', it has the potential to close a valid parentheses substring. In order to calculate the length of the longest valid parentheses substring that ends at a given index, we need to know the index of the last unmatched opening parenthesis '('.
The length of the valid substring ending at the current index can be calculated by taking the difference between the current index and the index of the last unmatched opening parenthesis.
Let's visualize a few examples to understand how that calculation works:
If there aren't any unmatched opening parentheses remaining after using the current closing parentheses, then we need to know the "start" of the current valid substring. Setting this value to -1 makes our calculation easier, as we can simply take the difference between the current index and the start of the valid substring to get the length.
However, if the closing parenthesis ')' doesn't close any valid substring (as shown below), then we can simply ignore it, and set the start of the current valid substring to the current index.
This leads us to the following algorithm:
- Initialize a stack. The stack will always contain the index of the last unmatched opening parenthesis, or the "start" of the current valid substring. Initially, the stack will contain -1 as the start of the current valid substring.
- Each time we encounter an opening parenthesis '(', we'll push its index onto the stack, which represents the index of the last unmatched opening parenthesis.
- Each time we encounter a closing parenthesis ')', we'll do the following:
-
We first pop the top element from the stack, as this closing parenthesis has the potential to close a valid parentheses substring.
-
Now, after popping, there are two possible cases:
-
The stack is not empty, and the top of the stack represents the index of the last unmatched opening parenthesis. We calculate the length of the valid substring ending at the current index by taking the difference between the current index and the index of the last unmatched opening parenthesis.
-
The stack is empty. This means that this closing parenthesis was unmatched. We'll update the start of the valid substring to the current index by pushing the current index onto the stack.
-
-
Solution
Visualization
Python
Try these examples:
def longest_valid_parentheses(s):max_len = 0stack = [-1]for i, char in enumerate(s):if char == '(':stack.append(i)else:stack.pop()if not stack:stack.append(i)else:max_len = max(max_len, i - stack[-1])return max_len
longest valid parentheses
0 / 17
Solution Visualization
Visualization
Python
Try these examples:
def longest_valid_parentheses(s):max_len = 0stack = [-1]for i, char in enumerate(s):if char == '(':stack.append(i)else:stack.pop()if not stack:stack.append(i)else:max_len = max(max_len, i - stack[-1])return max_len
longest valid parentheses
0 / 17
Walkthrough
Example 1: s = "(()())"
Initialization
We initialize our stack with [-1] as a sentinel value representing the start of the current valid substring, and set max_len = 0.
Visualization
longest valid parentheses
0 / 0
Push opening parentheses at indices 0 and 1
We encounter '(' at indices 0 and 1. For each, we push the index onto the stack. The stack now holds [-1, 0, 1] — both indices are waiting to be matched.
Visualization
checking character '(' at index 0
0 / 2
First match at index 2
We hit ')' at index 2. Pop index 1 from the stack — it's been matched. The top of the stack is now 0 (the last unmatched '('), so the valid substring length is 2 - 0 = 2. Update max_len = 2.
Visualization
checking character ')' at index 2
0 / 1
Push at index 3, then match at index 4
Index 3 is '(' — push it. Index 4 is ')' — pop index 3. The top of the stack is still 0, so the valid substring length is 4 - 0 = 4. Update max_len = 4.
Visualization
checking character '(' at index 3
0 / 3
Final match at index 5
The last ')' at index 5 pops index 0. Now the top of the stack is -1 (our sentinel). The valid substring length is 5 - (-1) = 6 — the entire string is valid. Update max_len = 6.
Visualization
checking character ')' at index 5
0 / 1
We return max_len = 6.
Example 2: s = ")())()()"
Unmatched ) at index 0
After initializing the stack with [-1], we immediately hit ')'. We pop -1, but now the stack is empty — this means the ) was unmatched. We push index 0 onto the stack as the new "start" marker.
Visualization
longest valid parentheses
0 / 3
Match () at indices 1–2
Push '(' at index 1. Then ')' at index 2 pops it. Top of stack is 0, so valid length is 2 - 0 = 2. Update max_len = 2.
Visualization
checking character '(' at index 1
0 / 3
Another unmatched ) at index 3
We hit ')' at index 3 and pop index 0. The stack is empty again — another unmatched ). Push index 3 as the new start marker. This resets where the next valid substring can begin.
Visualization
checking character ')' at index 3
0 / 1
Process ()() from indices 4–7
From index 4 onward, we process two consecutive pairs. Push 4, match at 5 (length 5 - 3 = 2). Push 6, match at 7 (length 7 - 3 = 4). Because both pairs are adjacent and share the same base marker at index 3, the length keeps growing. Update max_len = 4.
Visualization
checking character '(' at index 4
0 / 8
We return max_len = 4.
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n) where n is the length of the input string. We iterate over each character of the string once. At each character, we perform a constant amount of work.
Space Complexity: O(n) where n is the length of the input string. The stack can contain at most n elements (for example, if the input string is '(((((((((((').
Mark as read
Unlock Premium Coding Content
Reading Progress
On This Page
Your account is free and you can post anonymously if you choose.