32. Longest Valid Parentheses
1. Description
Given a string containing just the characters ‘(’ and ‘)’, return the length of the longest valid (well-formed) parentheses substring.
2. Example
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
3. Constraints
- 0 <= s.length <= $3 * 10^4$
- s[i] is ‘(’, or ‘)’.
4. Solutions
Dynamic Programming
n = str.size()
Time complexity: O(n)
Space complexity: O(n)
class Solution {
public:
int longestValidParentheses(const string &str) {
vector<int> valid_parentheses(str.size());
int result = 0;
for (size_t i = 1; i < str.size(); ++i) {
if (str[i] == ')') { // ()()()
if (str[i - 1] == '(') {
valid_parentheses[i] = (i - 2 >= 0 ? valid_parentheses[i - 2] : 0) + 2;
} else if ( // ((()))
i - valid_parentheses[i - 1] - 1 >= 0 &&
str[i - valid_parentheses[i - 1] - 1] == '(') {
valid_parentheses[i] = valid_parentheses[i - 1] +
(i - valid_parentheses[i - 1] - 2 >= 0
? valid_parentheses[i - valid_parentheses[i - 1] - 2]
: 0) +
2;
}
result = max(result, valid_parentheses[i]);
}
}
return result;
}
};
Two Side Iteration
n = str.size()
Time complexity: O(n)
Space complexity: O(1)
class Solution {
public:
int longestValidParentheses(const string &str) {
int result = 0;
// we can't use something like status to record the balance
// because we also need to know the number of parentheses pairs
for (int i = 0, left = 0, right = 0; i < str.size(); ++i) {
if (str[i] == '(') {
++left;
} else {
++right;
}
if (left == right) {
result = max(result, right * 2);
} else if (left < right) {
left = right = 0;
}
}
for (int i = str.size() - 1, left = 0, right = 0; i >= 0; --i) {
if (str[i] == ')') {
++right;
} else {
++left;
}
if (left == right) {
result = max(result, left * 2);
} else if (right < left) {
left = right = 0;
}
}
return result;
}
};