LeetCode Problem – Longest Valid Parentheses

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

substring.

Example 1:Input: s = “(()” Output: 2 Explanation: The longest valid parentheses substring is “()”.

Example 2:Input: s = “)()())” Output: 4 Explanation: The longest valid parentheses substring is “()()”.

Example 3:Input: s = “” Output: 0

Constraints:

• 0 <= s.length <= 3 * 104
• s[i] is '(', or ')'.

Java Solution

You can solve this problem using a stack to keep track of indices of unmatched parentheses. Here’s a Java solution for the given problem:

import java.util.Stack;

public class LongestValidParentheses {
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int maxLength = 0;

        for (int i = 0; i < s.length(); i++) {
            char currentChar = s.charAt(i);

            if (currentChar == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    maxLength = Math.max(maxLength, i - stack.peek());
                }
            }
        }

        return maxLength;
    }

    public static void main(String[] args) {
        LongestValidParentheses solution = new LongestValidParentheses();

        // Example 1
        String s1 = "(()";
        System.out.println("Example 1 Output: " + solution.longestValidParentheses(s1));

        // Example 2
        String s2 = ")()())";
        System.out.println("Example 2 Output: " + solution.longestValidParentheses(s2));

        // Example 3
        String s3 = "";
        System.out.println("Example 3 Output: " + solution.longestValidParentheses(s3));
    }
}

This program defines a LongestValidParentheses class with a longestValidParentheses method to find the length of the longest valid parentheses substring. The main method demonstrates how to use the program with the provided examples. The idea is to use a stack to keep track of the indices of unmatched parentheses and calculate the length of valid parentheses substrings by popping indices from the stack.

Python Solution

class LongestValidParentheses:
    def longestValidParentheses(self, s: str) -> int:
        stack = [-1]
        max_length = 0

        for i in range(len(s)):
            current_char = s[i]

            if current_char == '(':
                stack.append(i)
            else:
                stack.pop()
                if not stack:
                    stack.append(i)
                else:
                    max_length = max(max_length, i - stack[-1])

        return max_length

# Example usage:
solution = LongestValidParentheses()

# Example 1
s1 = "(()"
print("Example 1 Output:", solution.longestValidParentheses(s1))

# Example 2
s2 = ")()())"
print("Example 2 Output:", solution.longestValidParentheses(s2))

# Example 3
s3 = ""
print("Example 3 Output:", solution.longestValidParentheses(s3))

This Python code mirrors the Java solution. It defines a LongestValidParentheses class with a longestValidParentheses method to find the length of the longest valid parentheses substring. The example usage section demonstrates how to use the program with the provided examples. The idea is the same as the Java solution, using a stack to keep track of indices of unmatched parentheses.