LeetCode 32: Longest Valid Parentheses (Stack with Sentinel Index)
LeetCode 32StackStringInterviewToday we solve LeetCode 32 - Longest Valid Parentheses.
Source: https://leetcode.com/problems/longest-valid-parentheses/
English
Problem Summary
Given a string containing only ( and ), return the length of the longest contiguous substring that forms valid parentheses.
Key Insight
Store indices (not characters) in a stack, and keep a sentinel boundary index for the last unmatched right parenthesis. When a match exists, the current valid length is i - stack.peek().
Brute Force and Limitations
Checking every substring is O(n^3) or O(n^2) with pruning and still too slow. Stack indexing solves it in one pass.
Optimal Algorithm Steps
1) Push sentinel -1 into stack.
2) For each index i:
- If s[i] == '(', push i.
- Else pop once for matching attempt.
3) If stack becomes empty, push i as new boundary.
4) Otherwise update answer with i - stack.peek().
Complexity Analysis
Time: O(n).
Space: O(n) in worst case.
Common Pitfalls
- Forgetting initial sentinel -1.
- Popping from empty stack.
- Using character stack and losing length boundary information.
- Treating non-contiguous matched pairs as one segment.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int longestValidParentheses(String s) {
Deque<Integer> stack = new ArrayDeque<>();
stack.push(-1);
int ans = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
} else {
stack.pop();
if (stack.isEmpty()) {
stack.push(i);
} else {
ans = Math.max(ans, i - stack.peek());
}
}
}
return ans;
}
}func longestValidParentheses(s string) int {
stack := []int{-1}
ans := 0
for i, ch := range s {
if ch == '(' {
stack = append(stack, i)
} else {
stack = stack[:len(stack)-1]
if len(stack) == 0 {
stack = append(stack, i)
} else {
length := i - stack[len(stack)-1]
if length > ans {
ans = length
}
}
}
}
return ans
}class Solution {
public:
int longestValidParentheses(string s) {
stack<int> st;
st.push(-1);
int ans = 0;
for (int i = 0; i < (int)s.size(); ++i) {
if (s[i] == '(') {
st.push(i);
} else {
st.pop();
if (st.empty()) {
st.push(i);
} else {
ans = max(ans, i - st.top());
}
}
}
return ans;
}
};class Solution:
def longestValidParentheses(self, s: str) -> int:
stack = [-1]
ans = 0
for i, ch in enumerate(s):
if ch == '(':
stack.append(i)
else:
stack.pop()
if not stack:
stack.append(i)
else:
ans = max(ans, i - stack[-1])
return ansvar longestValidParentheses = function(s) {
const stack = [-1];
let ans = 0;
for (let i = 0; i < s.length; i++) {
if (s[i] === '(') {
stack.push(i);
} else {
stack.pop();
if (stack.length === 0) {
stack.push(i);
} else {
ans = Math.max(ans, i - stack[stack.length - 1]);
}
}
}
return ans;
};中文
题目概述
给定只包含 ( 和 ) 的字符串，返回最长连续合法括号子串的长度。
核心思路
栈里存“下标”而不是字符，并保留一个哨兵边界（最近未匹配右括号位置）。每次成功匹配后，当前合法长度就是 i - 栈顶下标。
暴力解法与不足
枚举所有子串并校验合法性时间复杂度高，最差可到 O(n^3)，面试与大输入都不实用。
最优算法步骤
1）先压入哨兵 -1。
2）遍历每个位置 i：
- 若是 (，压入 i。
- 若是 )，先弹栈尝试匹配。
3）若弹栈后为空，说明当前位置是新断点，压入 i 作为边界。
4）否则用 i - 栈顶 更新答案。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(n)。
常见陷阱
- 忘记初始化哨兵 -1。
- 右括号处理时可能对空栈弹出。
- 只存字符导致无法正确计算区间长度。
- 把不连续的匹配段错误拼成一个答案。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int longestValidParentheses(String s) {
Deque<Integer> stack = new ArrayDeque<>();
stack.push(-1);
int ans = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
} else {
stack.pop();
if (stack.isEmpty()) {
stack.push(i);
} else {
ans = Math.max(ans, i - stack.peek());
}
}
}
return ans;
}
}func longestValidParentheses(s string) int {
stack := []int{-1}
ans := 0
for i, ch := range s {
if ch == '(' {
stack = append(stack, i)
} else {
stack = stack[:len(stack)-1]
if len(stack) == 0 {
stack = append(stack, i)
} else {
length := i - stack[len(stack)-1]
if length > ans {
ans = length
}
}
}
}
return ans
}class Solution {
public:
int longestValidParentheses(string s) {
stack<int> st;
st.push(-1);
int ans = 0;
for (int i = 0; i < (int)s.size(); ++i) {
if (s[i] == '(') {
st.push(i);
} else {
st.pop();
if (st.empty()) {
st.push(i);
} else {
ans = max(ans, i - st.top());
}
}
}
return ans;
}
};class Solution:
def longestValidParentheses(self, s: str) -> int:
stack = [-1]
ans = 0
for i, ch in enumerate(s):
if ch == '(':
stack.append(i)
else:
stack.pop()
if not stack:
stack.append(i)
else:
ans = max(ans, i - stack[-1])
return ansvar longestValidParentheses = function(s) {
const stack = [-1];
let ans = 0;
for (let i = 0; i < s.length; i++) {
if (s[i] === '(') {
stack.push(i);
} else {
stack.pop();
if (stack.length === 0) {
stack.push(i);
} else {
ans = Math.max(ans, i - stack[stack.length - 1]);
}
}
}
return ans;
};
Comments