# Solution For 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:
Input: “(()”
Output: 2
Explanation: The longest valid parentheses substring is “()”

Input: “)()())”
Output: 4
Explanation: The longest valid parentheses substring is “()()”

Solution:

We can use dynamic programming to solve this problem. Let us define dp[i] as the length of the longest valid parentheses substring ending at index i in the given string.

To compute dp[i], we need to analyze the substring ending at index i. There are two cases:

1. If the substring ends with ‘(‘, then dp[i] must be 0, since no valid parentheses substring can end with ‘(‘.

2. If the substring ends with ‘)’ we need to consider its corresponding ‘(‘ in the string. Let ‘j’ be the index of the matching opening bracket for the closing bracket at index ‘i’. Then, we have two cases:

a. If j-1 >= 0, then dp[i] = dp[j-1] + 2, because the substring from j to i is a valid parenthese substring and we can also add the length of the valid subsequence ending at index j-1.

b. If j-1 < 0, then dp[i] = 2, because the first two characters of the given string form a valid parentheses substring (i.e “()”).

We can find the matching opening bracket for a given closing bracket in constant time using a stack. We push the index of the opening bracket onto the stack when we encounter it and pop the last element when we encounter a closing bracket.

The final answer is the maximum element in the dp array.

Pseudo-code for the algorithm:

1. Initialize an empty stack and a dp array of length n with all values as 0.
2. For i = 0 to n-1:
a. If s[i] = ‘(‘, push i onto the stack.
b. If s[i] = ‘)’ and stack is not empty, pop the top element.
i. If stack is empty, dp[i] = i+1, otherwise dp[i] = (i – stack.top())
c. Update the maximum length seen so far and update dp array.
3. Return maximum length seen so far.

Time Complexity: O(n), where n is the length of the given string s.

Space Complexity: O(n), where n is the length of the given string s.

Code in Python:

class Solution:
def longestValidParentheses(self, s: str) -> int:
stack = [-1] max_len = 0
n = len(s)
dp =  * n
for i in range(n):
if s[i] == ‘(‘:
stack.append(i)
else:
if stack and s[stack[-1]] == ‘(‘:
stack.pop()
if not stack:
dp[i] = i+1
else:
dp[i] = i – stack[-1] max_len = max(max_len, dp[i])
else:
stack.append(i)
return max_len

## Step by Step Implementation For Longest Valid Parentheses

```class Solution {
public int longestValidParentheses(String s) {
int maxans = 0;
Stack stack = new Stack<>();
stack.push(-1);
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
} else {
stack.pop();
if (stack.empty()) {
stack.push(i);
} else {
maxans = Math.max(maxans, i - stack.peek());
}
}
}
return maxans;
}
}```
```def longestValidParentheses(s):

# Base Case:
if len(s) <= 1:
return 0

# Initialize two counters
left = right = 0

# Initialize result
max_length = 0

# Iterate the given string
for i in range(len(s)):

# If opening bracket,
# then increment left counter
if s[i] == '(':
left+= 1

# Else if closing bracket,
# then increment right counter
else:
right+= 1

# If both left and right
# counters are equal,
# then we have a valid
# substring
if left == right:
max_length = i + 1

# If right counter is more,
# then reset both counters
elif right > left:
left = right = 0

# Check for remaining valid
# substring
if left == right:
return max_length

# Else reset both counters
left = right = 0

# Iterate given string
# in reverse direction
for i in range(len(s)-1, -1, -1):

# If opening bracket,
# then increment left counter
if s[i] == '(':
left+= 1

# Else if closing bracket,
# then increment right counter
else:
right+= 1

# If both left and right
# counters are equal,
# then we have a valid
# substring
if left == right:
max_length = len(s) - i

# If left counter is more,
# then reset both counters
elif left > right:
left = right = 0

return max_length```
```var longestValidParentheses = function(s) {
let maxans = 0;
let dp = new Array(s.length).fill(0);
for (let i = 1; i < s.length; i++) {
if (s[i] === ')') {
if (s[i - 1] === '(') {
dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
} else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] === '(') {
dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
}
maxans = Math.max(maxans, dp[i]);
}
}
return maxans;
};```
```class Solution {
public:
int longestValidParentheses(string s) {
// Base case
if (s.length() <= 1) {
return 0;
}

// Variables to keep track of the maximum length valid parentheses
// string and the current length of the valid parentheses string
int max_len = 0;
int curr_len = 0;

// Stack to keep track of the indices of the '(' characters
stack st;

// Iterate through the input string
for (int i = 0; i < s.length(); i++) {
// If the current character is a '(', push its index onto the stack
if (s[i] == '(') {
st.push(i);
}
// If the current character is a ')',
else {
// If the stack is empty, this means that there is no matching
// '(' character for the current ')' character, so we reset the
// current length of valid parentheses to 0
if (st.empty()) {
curr_len = 0;
}
// Otherwise, if the stack is not empty, this means that we have
// found a matching '(' character for the current ')' character
else {
// Pop the top element from the stack
st.pop();

// If the stack is now empty, this means that the current
// character is the first ')' character in a valid parentheses
// string, so we set the current length of valid parentheses
// to be the index of the current character plus 1
if (st.empty()) {
curr_len = i + 1;
}
// Otherwise, if the stack is not empty, this means that the
// current character is not the first ')' character in a valid
// parentheses string, so we set the current length of valid
// parentheses to be the difference between the index of the
// current character and the top element of the stack (which
// is the index of the last '(' character in the valid
// parentheses string) plus 1
else {
curr_len = i - st.top();
}

// Update the maximum length of valid parentheses if necessary
if (curr_len > max_len) {
max_len = curr_len;
}
}
}
}

// Return the maximum length of valid parentheses
return max_len;
}
};```
`using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication1 { class Program { static void Main(string[] args) { string s = ")()())"; // the input string Console.WriteLine(longestValidParentheses(s)); Console.ReadLine(); } public static int longestValidParentheses(string s) { int maxlen = 0; int last = -1; Stack left = new Stack(); for (int j = 0; j < s.Length; j++) { if (s[j] == '(') left.Push(j); else if (s[j] == ')') { if (left.Count == 0) last = j; else { left.Pop(); if (left.Count == 0) maxlen = Math.Max(maxlen, j - last); else maxlen = Math.Max(maxlen, j - left.Peek()); } } } return maxlen; } } }`

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]