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:
If the substring ends with ‘(‘, then dp[i] must be 0, since no valid parentheses substring can end with ‘(‘.
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:
- Initialize an empty stack and a dp array of length n with all values as 0.
- 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. - 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 = [0] * 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; Stackstack = 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 stackst; // 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; Stackleft = 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; } } }