Problem
Given a string with only ( and ), find the length of the longest valid (well-formed) parentheses substring.
Example
Input: ")()())"
Output: 4
"()()" is the longest valid substring.Solution
Stack of indices. Push -1 as base. For (, push index. For ), pop. If stack empty, push current. Otherwise update max.
def longest_valid_parentheses(s):
stack = [-1]
max_len = 0
for i, ch in enumerate(s):
if ch == '(':
stack.append(i)
else:
stack.pop()
if not stack: stack.append(i)
else: max_len = max(max_len, i - stack[-1])
return max_lenfunction longestValidParentheses(s) {
const stack = [-1];
let maxLen = 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 maxLen = Math.max(maxLen, i - stack[stack.length-1]);
}
}
return maxLen;
}int longestValidParentheses(string s) {
stack<int> st;
st.push(-1);
int maxLen = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(') st.push(i);
else {
st.pop();
if (st.empty()) st.push(i);
else maxLen = max(maxLen, i - st.top());
}
}
return maxLen;
}public int longestValidParentheses(String s) {
Stack<Integer> st = new Stack<>();
st.push(-1);
int maxLen = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') st.push(i);
else {
st.pop();
if (st.isEmpty()) st.push(i);
else maxLen = Math.max(maxLen, i - st.peek());
}
}
return maxLen;
}Complexity
- Time: O(n)
- Space: O(n)
Explanation
The base -1 lets us measure length from the start. When stack becomes empty after popping, we have an unmatched ); use it as the new base.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?