The challenge
Return the length of the longest contiguous well-formed parentheses substring.
Input contains only ( and ). Empty input returns 0.
Example
)()()) → 4.
Use the walkthrough below to inspect the input and each state change.
See Longest Valid Parentheses, step by step
Inspect each push, pop, and recorded answer. Entries such as 2: 5 mean index: value.
Zero-based input · top labeled explicitlyLIFO
- Current input index
- —
- Main stack size
- 0
Step 01 / 9
Start with an empty stack
Read the input in order. The stack keeps only the state needed to resolve the next item.
Answer so far
Not recorded yet
- Main stack · bottom → top
- Empty
- Auxiliary stack · bottom → top
- Empty
View exact input and state
Input: [")","(",")","(",")",")"]
Main stack: []. Auxiliary stack · bottom → top: [].
Put it into code
Start with boundary −1; an unmatched closer becomes the new boundary.
Indices are zero-based. C++ uses C++17 or later.
def solve(values):
stack, best = [-1], 0
for i, c in enumerate(values):
if c == '(': stack.append(i)
else:
stack.pop()
if not stack: stack.append(i)
else: best = max(best, i - stack[-1])
return best
#include <algorithm>
#include <optional>
#include <utility>
#include <string>
#include <vector>
using namespace std;
int solve(const vector<string>& values) {
vector<int> stack = {-1};
int best = 0;
for (int i = 0; i < static_cast<int>(values.size()); ++i) {
if (values[i] == "(") stack.push_back(i);
else {
stack.pop_back();
if (stack.empty()) stack.push_back(i);
else best = max(best, i - stack.back());
}
}
return best;
}