0032. Longest Valid Parentheses
https://leetcode.com/problems/longest-valid-parentheses
Description
Given a string containing just the characters '('
and ')'
, find the length of the longest valid (well-formed) parentheses substring.
Example 1:
**Input:** s = "(()"
**Output:** 2
**Explanation:** The longest valid parentheses substring is "()".
Example 2:
**Input:** s = ")()())"
**Output:** 4
**Explanation:** The longest valid parentheses substring is "()()".
Example 3:
**Input:** s = ""
**Output:** 0
Constraints:
0 <= s.length <= 3 * 104
s[i]
is'('
, or')'
.
ac1: stack
parentheses -> stack
class Solution {
public int longestValidParentheses(String s) {
// edge case
if (s == null | s.length() < 2) return 0;
// iterate
Stack<Integer> stack = new Stack<Integer>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == ')' && !stack.isEmpty() && s.charAt(stack.peek()) == '(') {
stack.pop();
} else {
stack.push(i);
}
}
stack.push(s.length());
// check remaining indices
int max = 0, curr = stack.pop();
while (!stack.isEmpty()) {
int next = stack.pop();
max = Math.max(max, curr - next - 1);
curr = next;
}
max = Math.max(max, curr - 0); // check last one
// result
return max;
}
}
/*
parentheses -> stack
iterate, if '(' push to stack, if ')' check:
if stack.peek() == '(', stack.pop(), kill one pair parentheses
else push
stack record indices
finally check remaining indices, record longest one
*/
ac2: 2 pointers
class Solution {
public int longestValidParentheses(String s) {
// edge case
if (s == null | s.length() < 2) return 0;
int max = 0;
// iterate, keep track of left bracket & right bracket
int l = 0, r = 0;
// 1st, left -> right
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') l++;
else r++;
if (l == r) {
max = Math.max(max, l * 2);
}
else if (l < r) {
l = 0;
r = 0;
}
}
// 2nd, right -> left
l = 0; r = 0;
for (int i = s.length() - 1; i >= 0; i--) {
char c = s.charAt(i);
if (c == '(') l++;
else r++;
if (l == r) {
max = Math.max(max, l * 2);
}
else if (l > r) {
l = 0;
r = 0;
}
}
// result
return max;
}
}
/*
2 pointers
keep track of left bracket & right bracket: meet ( left++, meet ) right++
when left = right, means valid parentheses, track length
if left < right, invalid, pass, set 0 to restart
2 pass, left -> right, then right -> left. because 1 pass cannot track those when left > right
*/
ac3: DP
class Solution {
public int longestValidParentheses(String s) {
// edge case
if (s == null | s.length() < 2) return 0;
int max = 0;
// dp
int[] dp = new int[s.length()];
for (int i = 1; i < dp.length; i++) {
char c = s.charAt(i);
if (c == ')') {
int prev = i - dp[i-1] - 1; // careful boundary
if (prev >= 0 && s.charAt(prev) == '(') {
dp[i] = 2 + dp[i-1] + (prev > 0 ? dp[prev-1] : 0);
max = Math.max(max, dp[i]);
}
}
}
// result
return max;
}
}
/*
DP
state: dp[i], the length of valid parentheses end with current index
function:
meet (, dp[i] = 0, do nothing
meet ),
if s.charAt(i-1) == '(', dp[i] = dp[i-1] + 2
if i - dp[i-1] - 1 is '(', dp[i] = 2 + dp[i-1] + dp[i - dp[i-1] - 2]
*/
Last updated