Longest Valid Parentheses - Java Solution

1. Introduction

This blog post explores a challenging problem in string processing - finding the length of the longest valid (well-formed) parentheses substring. This problem is a common question in interviews and competitive programming, requiring an understanding of stack data structures or dynamic programming to solve efficiently.

Problem

Given a string containing just the characters '(' and ')', the task is to determine the length of the longest substring that is a valid parentheses sequence. A valid parentheses sequence is defined as one where each opening parenthesis '(' has a corresponding closing parenthesis ')'.

2. Solution Steps

1. Use a stack to keep track of indices of parentheses.

2. Iterate through the characters of the string.

3. If an opening parenthesis is encountered, push its index onto the stack.

4. If a closing parenthesis is encountered, pop from the stack:

a. If the stack becomes empty, push the current index onto the stack.

b. If the stack is not empty, calculate the length of the current valid substring and update the maximum length.

5. Return the maximum length found.

3. Code Program

public class LongestValidParentheses {
    public static void main(String[] args) {
        String s = "(()";
        System.out.println(longestValidParentheses(s)); // Test the function
    }

    // Function to find the length of the longest valid parentheses substring
    public static int longestValidParentheses(String s) {
        int maxLen = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.empty()) {
                    stack.push(i);
                } else {
                    maxLen = Math.max(maxLen, i - stack.peek());
                }
            }
        }
        return maxLen;
    }
}

Output:

2

Explanation:

1. longestValidParentheses: This function computes the length of the longest valid parentheses substring in the given string s.

2. It initializes a stack to keep track of the indices of parentheses.

3. As the string is iterated, indices of opening parentheses are pushed onto the stack.

4. When a closing parenthesis is encountered, an index is popped from the stack:

a. If the stack is empty after popping, the current index is pushed onto the stack.

b. If the stack is not empty, the length of the valid substring ending at the current index is calculated as i - stack.peek(), and maxLen is updated if this length is greater.

5. The function returns the maximum length of a valid parentheses substring found during the iteration.

6. This approach efficiently identifies the longest valid substring by using a stack to balance the parentheses and calculate lengths.