# 32. Longest Valid Parentheses

## Description

Given a string containing just the characters '(' and ')', return 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 ')'.

## Solutions

Solution 1: Dynamic Programming

We define $f[i]$ to be the length of the longest valid parentheses that ends with $s[i-1]$, and the answer is $max(f[i])$.

When $i \lt 2$, the length of the string is less than $2$, and there is no valid parentheses, so $f[i] = 0$.

When $i \ge 2$, we consider the length of the longest valid parentheses that ends with $s[i-1]$, that is, $f[i]$:

• If $s[i-1]$ is a left parenthesis, then the length of the longest valid parentheses that ends with $s[i-1]$ must be $0$, so $f[i] = 0$.
• If $s[i-1]$ is a right parenthesis, there are the following two cases:
• If $s[i-2]$ is a left parenthesis, then the length of the longest valid parentheses that ends with $s[i-1]$ is $f[i-2] + 2$.
• If $s[i-2]$ is a right parenthesis, then the length of the longest valid parentheses that ends with $s[i-1]$ is $f[i-1] + 2$, but we also need to consider whether $s[i-f[i-1]-2]$ is a left parenthesis. If it is a left parenthesis, then the length of the longest valid parentheses that ends with $s[i-1]$ is $f[i-1] + 2 + f[i-f[i-1]-2]$.

Therefore, we can get the state transition equation:

$\begin{cases} f[i] = 0, & \text{if } s[i-1] = '(',\\ f[i] = f[i-2] + 2, & \text{if } s[i-1] = ')' \text{ and } s[i-2] = '(',\\ f[i] = f[i-1] + 2 + f[i-f[i-1]-2], & \text{if } s[i-1] = ')' \text{ and } s[i-2] = ')' \text{ and } s[i-f[i-1]-2] = '(',\\ \end{cases}$

Finally, we only need to return $max(f)$.

The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of the string.

Solution 2: Using Stack

• Maintain a stack to store the indices of left parentheses. Initialize the bottom element of the stack with the value -1 to facilitate the calculation of the length of valid parentheses.
• Iterate through each element of the string:
• If the character is a left parenthesis, push the index of the character onto the stack.
• If the character is a right parenthesis, pop an element from the stack to represent that we have found a valid pair of parentheses.
• If the stack is empty, it means we couldn’t find a left parenthesis to match the right parenthesis. In this case, push the index of the character as a new starting point.
• If the stack is not empty, calculate the length of the valid parentheses and update it.

Summary:

The key to this algorithm is to maintain a stack to store the indices of left parentheses and then update the length of the valid substring of parentheses by pushing and popping elements.

The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of the string.

• class Solution {
public int longestValidParentheses(String s) {
int n = s.length();
int[] f = new int[n + 1];
int ans = 0;
for (int i = 2; i <= n; ++i) {
if (s.charAt(i - 1) == ')') {
if (s.charAt(i - 2) == '(') {
f[i] = f[i - 2] + 2;
} else {
int j = i - f[i - 1] - 1;
if (j > 0 && s.charAt(j - 1) == '(') {
f[i] = f[i - 1] + 2 + f[j - 1];
}
}
ans = Math.max(ans, f[i]);
}
}
return ans;
}
}

//////

class Solution_noExtraSpace {
public int longestValidParentheses(String s) {
int res = 0, left = 0, right = 0, n = s.length();

// from left to right, '(()' => will never hit left==right
for (int i = 0; i < n; ++i) {
if (s.charAt(i) == '(') ++left;
else ++right;

if (left == right) res = Math.max(res, 2 * right);
else if (right > left) left = right = 0;
}

// from right to left, '())' => will never hit left==right
left = right = 0;
for (int i = n - 1; i >= 0; --i) {
if (s.charAt(i) == '(') ++left;
else ++right;

if (left == right) res = Math.max(res, 2 * left);
else if (left > right) left = right = 0;
}
return res;

}
}

//////

class Solution_stack {
public int longestValidParentheses(String s) {
Stack<Integer> sk = new Stack<>();
int start = 0;
int result = 0;
for (int i = 0;i < s.length(); i++) {
if(s.charAt(i) == '(') {
sk.push(i);
} else {
if (sk.empty()) {
start = i + 1;
} else {
sk.pop();
result = Math.max(result, sk.isEmpty() ? i - start + 1 : i - sk.peek());
}
}
}
return result;

}
}


• class Solution {
public:
int longestValidParentheses(string s) {
int n = s.size();
int f[n + 1];
memset(f, 0, sizeof(f));
for (int i = 2; i <= n; ++i) {
if (s[i - 1] == ')') {
if (s[i - 2] == '(') {
f[i] = f[i - 2] + 2;
} else {
int j = i - f[i - 1] - 1;
if (j && s[j - 1] == '(') {
f[i] = f[i - 1] + 2 + f[j - 1];
}
}
}
}
return *max_element(f, f + n + 1);
}
};

• class Solution:
def longestValidParentheses(self, s: str) -> int:
left = right = 0
res = 0
for c in s: # from left to right, '(()' => will never hit left==right
if c == '(':
left += 1
else:
right += 1
if left == right:
res = max(res, 2 * left)
if left < right:
left = right = 0

left = right = 0 # dont forget to reset
for c in reversed(s): # from right to left, '())' => will never hit left==right
if c == '(':
left += 1
else:
right += 1
if left == right:
res = max(res, 2 * left)
if left > right: # reverse '<' to '>'
left = right = 0

return res

######

class Solution:
def longestValidParentheses(self, s: str) -> int:
n = len(s)
if n < 2:
return 0
dp = [0] * n
for i in range(1, n):
if s[i] == ')':
if s[i - 1] == '(':
dp[i] = 2 + (dp[i - 2] if i > 1 else 0)
else:
j = i - dp[i - 1] - 1
if j >= 0 and s[j] == '(':
dp[i] = 2 + dp[i - 1] + dp[j - 1]
return max(dp)

######

'''
>>> s="abcdefg"
>>> [print(i,",",c) for i, c in enumerate(s, 1)]
1 , a
2 , b
3 , c
4 , d
5 , e
6 , f
7 , g
[None, None, None, None, None, None, None]
>>>
'''
class Solution:
def longestValidParentheses(self, s: str) -> int:
n = len(s)
f = [0] * (n + 1)
for i, c in enumerate(s, 1): # starting i from 1, not 0
if c == ")":
if i > 1 and s[i - 2] == "(":
f[i] = f[i - 2] + 2
else:
j = i - f[i - 1] - 1
if j and s[j - 1] == "(":
f[i] = f[i - 1] + 2 + f[j - 1]
return max(f)


• func longestValidParentheses(s string) int {
n := len(s)
f := make([]int, n+1)
for i := 2; i <= n; i++ {
if s[i-1] == ')' {
if s[i-2] == '(' {
f[i] = f[i-2] + 2
} else if j := i - f[i-1] - 1; j > 0 && s[j-1] == '(' {
f[i] = f[i-1] + 2 + f[j-1]
}
}
}
return slices.Max(f)
}

• function longestValidParentheses(s: string): number {
const n = s.length;
const f: number[] = new Array(n + 1).fill(0);
for (let i = 2; i <= n; ++i) {
if (s[i - 1] === ')') {
if (s[i - 2] === '(') {
f[i] = f[i - 2] + 2;
} else {
const j = i - f[i - 1] - 1;
if (j && s[j - 1] === '(') {
f[i] = f[i - 1] + 2 + f[j - 1];
}
}
}
}
return Math.max(...f);
}


• /**
* @param {string} s
* @return {number}
*/
var longestValidParentheses = function (s) {
const n = s.length;
const f = new Array(n + 1).fill(0);
for (let i = 2; i <= n; ++i) {
if (s[i - 1] === ')') {
if (s[i - 2] === '(') {
f[i] = f[i - 2] + 2;
} else {
const j = i - f[i - 1] - 1;
if (j && s[j - 1] === '(') {
f[i] = f[i - 1] + 2 + f[j - 1];
}
}
}
}
return Math.max(...f);
};


• public class Solution {
public int LongestValidParentheses(string s) {
int n = s.Length;
int[] f = new int[n + 1];
int ans = 0;
for (int i = 2; i <= n; ++i) {
if (s[i - 1] == ')') {
if (s[i - 2] == '(') {
f[i] = f[i - 2] + 2;
} else {
int j = i - f[i - 1] - 1;
if (j > 0 && s[j - 1] == '(') {
f[i] = f[i - 1] + 2 + f[j - 1];
}
}
ans = Math.Max(ans, f[i]);
}
}
return ans;
}
}

• impl Solution {
pub fn longest_valid_parentheses(s: String) -> i32 {
let mut ans = 0;
let mut f = vec![0; s.len() + 1];
for i in 2..=s.len() {
if
s
.chars()
.nth(i - 1)
.unwrap() == ')'
{
if
s
.chars()
.nth(i - 2)
.unwrap() == '('
{
f[i] = f[i - 2] + 2;
} else if
(i as i32) - f[i - 1] - 1 > 0 &&
s
.chars()
.nth(i - (f[i - 1] as usize) - 2)
.unwrap() == '('
{
f[i] = f[i - 1] + 2 + f[i - (f[i - 1] as usize) - 2];
}
ans = ans.max(f[i]);
}
}
ans
}
}


• class Solution {
/**
* @param string $s * @return integer */ function longestValidParentheses($s) {
$stack = [];$maxLength = 0;

array_push($stack, -1); for ($i = 0; $i < strlen($s); $i++) { if ($s[$i] === '(') { array_push($stack, $i); } else { array_pop($stack);

if (empty($stack)) { array_push($stack, $i); } else {$length = $i - end($stack);
$maxLength = max($maxLength, $length); } } } return$maxLength;
}
}