LeetCode - Longest Valid Parentheses
Problem description
Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.
Example 1:
1
2
3
Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"
Example 2:
1
2
3
Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"
Analysis
Basic idea is to scan the array twice, one from start to end, one from end to start to find cases like “())))” and “((()” respectively. One-pass is also fine, but you have to consider two situations.
Here’s the code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class LongestValidParentheses {
public int longestValidParentheses(String s) {
int max = 0;
int val = 0;
int start = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
val++;
} else {
val--;
}
if (val == 0) {
max = Math.max(max, i - start + 1);
} else if (val < 0) {
start = i + 1;
val = 0;
}
}
start = s.length() - 1;
val = 0;
for (int i = s.length() - 1; i >= 0; i--) {
if (s.charAt(i) == ')') {
val++;
} else {
val--;
}
if (val == 0) {
max = Math.max(max, start - i + 1);
} else if (val < 0) {
start = i - 1;
val = 0;
}
}
return max;
}
}
Another solution is the DP solution from LeetCode, basic idea is to use dp[i] to indicate len of longest valid parentheses end at index i, here’s the code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int longestValidParentheses(String s) {
int maxLength = 0;
int[] dp = new int[s.length()];
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == ')') {
if (s.charAt(i-1) == '(') {
dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;
} else if (i - dp[i-1] > 0 && s.charAt(i-dp[i-1]-1) == '(') {
dp[i] = dp[i-1] + ((i - dp[i-1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
}
maxLength = Math.max(maxLength, dp[i]);
}
}
return maxLength;
}
}