32. Longest Valid Parentheses (Hard)
https://leetcode.com/problems/longest-valid-parentheses/
Given a string containing just the characters '('
and ')'
, find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"
Example 2:
Input: ")()())
" Output: 4 Explanation: The longest valid parentheses substring is"()()"
Solutions
class Solution {
public int longestValidParentheses(String s) {
Stack<Integer> stack = new Stack<>();
// Keep the track of ith char whether s.char[i] is part of a valid parenthese pair or not.
boolean[] track = new boolean[s.length()];
Arrays.fill(track, false);
// sort out all the valid parenthese pairs
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
}
// if s.charAt(index) matches s.char(i) and for a valid pair, set both track[i]
// and track[index] true
if (s.charAt(i) == ')' && !stack.isEmpty()) {
int j = stack.pop();
track[i] = true;
track[j] = true;
}
}
int max = 0;
// sort out the consecutive elements that are able to form valid parentheses pairs
int count = 0;
for (int i = 0; i < track.length; i++) {
if (track[i]) {
count++;
} else {
max = Math.max(max, count);
count = 0;
}
}
return Math.max(max, count);
}
}
Incorrect Solutions
class Solution {
// TODO Incorrect solution
// "()(()" expected 2, output 4
// The key idea of solving this problem is using stack
public int longestValidParentheses(String s) {
if (s == null || s.length() <= 1) {
return 0;
}
Stack<Character> stack = new Stack<>();
int max = 0;
int count = 0;
int len = s.length();
for (int i = 0; i < len; i++) {
// if it is open parenthese, push into stack
if (s.charAt(i) == '(') {
stack.push('(');
continue;
}
// if the ith char is ')' and stack is not empty, we can form a valid pair of parenthese
if (s.charAt(i) == ')' && !stack.isEmpty()) {
stack.pop();
count += 2;
max = Math.max(count, max);
}
// mal-formed
else if (s.charAt(i) == ')' && stack.isEmpty()) {
count = 0;
stack.clear();
}
}
return max;
}
}