Longest Valid parentheses

XXX. Longest Valid Parentheses

Stack

String

Dynamic Programming

Problem Statement:

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

Algorithm:

1. Initialize a stack to keep track of indices of unmatched parentheses.
2. Push -1 onto the stack to serve as a base index for valid substrings.
3. Iterate through the string:
• If the current character is '(', push its index onto the stack.
• If the current character is ')', pop the top of the stack:
• If the stack becomes empty, push the current index onto the stack as the new base index.
• Otherwise, calculate the length of the current valid substring as the difference between the current index and the top of the stack. Update the maximum length if necessary.
4. Return the maximum length of valid parentheses substring.

Complexity:

Time Complexity: O(n), where n is the length of the string. Each character is processed once.
Space Complexity: O(n), for the stack that stores indices.

Java Implementation:

public class Solution {
    public int longestValidParentheses(String s) {
        // Initialize variables
        int max = 0; // Maximum length of valid parentheses substring
        Stack stack = new Stack<>(); // Stack to track indices
        stack.push(-1); // Base index for valid substrings

        // Iterate through the string
        for (int i = 0; i < s.length(); i++) {
            // If the character is '(', push its index onto the stack
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                // If the character is ')', pop the top of the stack
                stack.pop();

                // If the stack is empty, push the current index as the new base index
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    // Calculate the length of the current valid substring
                    max = Math.max(max, i - stack.peek());
                }
            }
        }

        return max; // Return the maximum length
    }
}
                

Python Implementation:

def longest_valid_parentheses(s: str) -> int:
    # Initialize variables
    max_length = 0  # Maximum length of valid parentheses substring
    stack = [-1]  # Stack to track indices, initialized with base index

    # Iterate through the string
    for i, char in enumerate(s):
        if char == '(':
            # If the character is '(', push its index onto the stack
            stack.append(i)
        else:
            # If the character is ')', pop the top of the stack
            stack.pop()

            # If the stack is empty, push the current index as the new base index
            if not stack:
                stack.append(i)
            else:
                # Calculate the length of the current valid substring
                max_length = max(max_length, i - stack[-1])

    return max_length  # Return the maximum length
                

C++ Implementation:

#include 
#include 
#include 
using namespace std;

class Solution {
public:
    int longestValidParentheses(string s) {
        // Initialize variables
        int maxLength = 0; // Maximum length of valid parentheses substring
        stack stk; // Stack to track indices
        stk.push(-1); // Base index for valid substrings

        // Iterate through the string
        for (int i = 0; i < s.length(); ++i) {
            if (s[i] == '(') {
                // If the character is '(', push its index onto the stack
                stk.push(i);
            } else {
                // If the character is ')', pop the top of the stack
                stk.pop();

                // If the stack is empty, push the current index as the new base index
                if (stk.empty()) {
                    stk.push(i);
                } else {
                    // Calculate the length of the current valid substring
                    maxLength = max(maxLength, i - stk.top());
                }
            }
        }

        return maxLength; // Return the maximum length
    }
};