Longest Valid Parentheses In C,CPP,JAVA,PYTHON,C#,JS

Problem Statement:

Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.

A valid parentheses string is:

1. () is valid.
2. If A is valid, then ()A and A() are valid.
3. If A and B are valid, then AB is valid.

Example:

Example 1:

• Input: s = "(()"
• Output: 2
• Explanation: The longest valid parentheses substring is "()", which has length 2.

Example 2:

• Input: s = ")()())"
• Output: 4
• Explanation: The longest valid parentheses substring is "()()", which has length 4.

Example 3:

• Input: s = ""
• Output: 0
• Explanation: There is no valid parentheses substring.

Approach (Using Dynamic Programming):

1. State Definition:
   • Let dp[i] represent the length of the longest valid parentheses substring ending at index i.
2. Transition:
   • If s[i] == ')', check the character before it:
     • If s[i-1] == '(', then the substring s[i-1:i+1] is valid, and dp[i] = dp[i-2] + 2.
     • If s[i-1] == ')', check if s[i-dp[i-1]-1] == '('. If so, dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2].
3. Initialization:
   • dp[0] = 0 because there’s no valid substring ending at index 0.
4. Final Answer:
   • The result is the maximum value in the dp array.

Time Complexity:

• Time Complexity: O(n), where n is the length of the string s. We are processing each character of the string once.
• Space Complexity: O(n), for storing the DP array.

---

Code in Different Languages:

1. C

#include <stdio.h>
#include <string.h>

int longestValidParentheses(char* s) {
    int n = strlen(s);
    int dp[n];
    memset(dp, 0, sizeof(dp));
    int maxLength = 0;

    for (int i = 1; i < n; i++) {
        if (s[i] == ')') {
            if (s[i - 1] == '(') {
                dp[i] = (i - 2 >= 0) ? dp[i - 2] + 2 : 2;
            } else if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(') {
                dp[i] = dp[i - 1] + 2 + ((i - dp[i - 1] - 2 >= 0) ? dp[i - dp[i - 1] - 2] : 0);
            }
            maxLength = (dp[i] > maxLength) ? dp[i] : maxLength;
        }
    }

    return maxLength;
}

int main() {
    char s[] = ")()())";
    printf("Longest Valid Parentheses Length: %d\n", longestValidParentheses(s));
    return 0;
}

2. C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int longestValidParentheses(string s) {
    int n = s.size();
    vector<int> dp(n, 0);
    int maxLength = 0;

    for (int i = 1; i < n; i++) {
        if (s[i] == ')') {
            if (s[i - 1] == '(') {
                dp[i] = (i - 2 >= 0) ? dp[i - 2] + 2 : 2;
            } else if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(') {
                dp[i] = dp[i - 1] + 2 + ((i - dp[i - 1] - 2 >= 0) ? dp[i - dp[i - 1] - 2] : 0);
            }
            maxLength = max(maxLength, dp[i]);
        }
    }

    return maxLength;
}

int main() {
    string s = ")()())";
    cout << "Longest Valid Parentheses Length: " << longestValidParentheses(s) << endl;
    return 0;
}

3. Java

public class LongestValidParentheses {
    public static int longestValidParentheses(String s) {
        int n = s.length();
        int[] dp = new int[n];
        int maxLength = 0;

        for (int i = 1; i < n; i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i - 2 >= 0) ? dp[i - 2] + 2 : 2;
                } else if (i - dp[i - 1] - 1 >= 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1] + 2 + ((i - dp[i - 1] - 2 >= 0) ? dp[i - dp[i - 1] - 2] : 0);
                }
                maxLength = Math.max(maxLength, dp[i]);
            }
        }

        return maxLength;
    }

    public static void main(String[] args) {
        String s = ")()())";
        System.out.println("Longest Valid Parentheses Length: " + longestValidParentheses(s));
    }
}

4. Python

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

# Example usage
s = ")()())"
print(f"Longest Valid Parentheses Length: {longestValidParentheses(s)}")

5. C#

using System;

public class Solution {
    public int LongestValidParentheses(string s) {
        int n = s.Length;
        int[] dp = new int[n];
        int maxLength = 0;

        for (int i = 1; i < n; i++) {
            if (s[i] == ')') {
                if (s[i - 1] == '(') {
                    dp[i] = (i - 2 >= 0) ? dp[i - 2] + 2 : 2;
                } else if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(') {
                    dp[i] = dp[i - 1] + 2 + ((i - dp[i - 1] - 2 >= 0) ? dp[i - dp[i - 1] - 2] : 0);
                }
                maxLength = Math.Max(maxLength, dp[i]);
            }
        }

        return maxLength;
    }
    
    public static void Main(string[] args) {
        Solution solution = new Solution();
        string s = ")()())";
        Console.WriteLine($"Longest Valid Parentheses Length: {solution.LongestValidParentheses(s)}");
    }
}

6. JavaScript

var longestValidParentheses = function(s) {
    const n = s.length;
    const dp = Array(n).fill(0);
    let maxLength = 0;

    for (let i = 1; i < n; i++) {
        if (s[i] === ')') {
            if (s[i - 1] === '(') {
                dp[i] = (i - 2 >= 0) ? dp[i - 2] + 2 : 2;
            } else if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] === '(') {
                dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0);
            }
            maxLength = Math.max(maxLength, dp[i]);
        }
    }

    return maxLength;
};

// Example usage
const s = ")()())";
console.log("Longest Valid Parentheses Length:", longestValidParentheses(s));

---

Summary:

• Time Complexity: O(n), where n is the length of the string s.
• Space Complexity: O(n), due to the dp array used for storing the lengths of valid parentheses substrings.