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 = [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;
        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; } } }