Algorithm
Problem Name: 32. Longest Valid Parentheses
Problem Link: https://leetcode.com/problems/longest-valid-parentheses/
Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses
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 * 104s[i]is'(', or')'.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int longestValidParentheses(char* s) {
int i, l, n, *v;
int max;
if (!s) return 0;
l = strlen(s);
v = malloc(l * sizeof(int));
//assert(v);
n = 0;
for (i = 0; i < l; i ++) {
if (s[i] == '(') {
v[i] = 1;
n ++;
} else /*if (s[i] == ')')*/ {
if (n > 0) {
n --;
v[i] = 1;
} else {
v[i] = 0;
}
}
}
n = 0;
for (i = l - 1; i >= 0; i --) {
if (s[i] == ')') {
if (v[i]) {
n ++;
}
} else /*if (s[i] == '(')*/ {
if (n > 0) {
n --;
} else {
v[i] = 0;
}
}
}
n = 0; max = 0;
for (i = 1; i < l; i ++) {
if (v[i]) {
v[i] = v[i - 1] + 1;
if (max < v[i]) {
max = v[i];
}
}
}
free(v);
return max;
}
Input
s = "(()"
Output
2
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int longestValidParentheses(String s) {
int maxLength = 0;
int leftIdx = 0;
int rightIdx = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
leftIdx++;
} else {
rightIdx++;
}
if (leftIdx == rightIdx) {
maxLength = Math.max(maxLength, 2 * rightIdx);
} else if (rightIdx > leftIdx) {
leftIdx = rightIdx = 0;
}
}
leftIdx = 0;
rightIdx = 0;
for (int i = s.length() - 1; i >= 0; i--) {
if (s.charAt(i) == '(') {
leftIdx++;
} else {
rightIdx++;
}
if (leftIdx == rightIdx) {
maxLength = Math.max(maxLength, 2 * rightIdx);
} else if (leftIdx > rightIdx) {
leftIdx = rightIdx = 0;
}
}
return maxLength;
}
}
Input
s = ")()())"
Output
4
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const longestValidParentheses = function(s) {
const arr = s.split("")
const dp = new Array(arr.length).fill(0)
let open = 0
let max = 0
for (let i = 0; i < arr.length; i++) {
if (arr[i] === "(") open++
if (arr[i] === ")" && open > 0) {
dp[i] = 2 + dp[i - 1]
if (i - dp[i] > 0) dp[i] += dp[i - dp[i]]
open--
}
if (dp[i] > max) max = dp[i]
}
return max
}
Input
s = ""
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def longestValidParentheses(self, s):
stack, mx = [], 0
for i, c in enumerate(s):
if c == ")" and stack and s[stack[-1]] == "(": stack.pop()
else: stack.append(i)
stack = [-1] + stack + [len(s)]
for i1, i2 in zip(stack, stack[1:]): mx = max(mx, i2 - i1 - 1)
return mx if len(stack) > 2 else len(s)
Input
s = "(()"
Output
2
#5 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _032_LongestValidParentheses
{
public int LongestValidParentheses(string s)
{
int i, maxLen = 0, lastError = -1, depth = 0;
for (i = 0; i < s.Length; i++)
{
if (s[i] == '(') { depth++; }
else
{
depth--;
if (depth < 0)
{
depth = 0;
lastError = i;
}
else if (depth == 0)
{
maxLen = maxLen < i - lastError ? i - lastError : maxLen;
}
}
}
lastError = s.Length;
depth = 0;
for (i = s.Length - 1; i >= 0; i--)
{
if (s[i] == ')') { depth++; }
else
{
depth--;
if (depth < 0)
{
depth = 0;
lastError = i;
}
else if (depth == 0)
{
maxLen = maxLen < lastError - i ? lastError - i : maxLen;
}
}
}
return maxLen;
}
}
}
Input
s = ")()())"
Output
4