Longest Valid Parentheses – Leetcode 32 Solution

The Longest Valid Parentheses Leetcode problem is a classic string problem that tests your ability to work with parentheses and logic structures. Here’s the problem statement:

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

This blog post will walk you through several approaches to solve this problem, starting from the naive brute-force method and progressing to the optimal dynamic programming and stack-based solutions. All examples are implemented in Java.

Problem Analysis for Longest Valid Parentheses

A valid parentheses substring is one where:

• Each opening parenthesis '(' has a corresponding closing parenthesis ')'.
• The order of parentheses is correct.

Examples:

• "(()": Longest valid substring is "()" with length 2.
• ")()())": Longest valid substring is "()()" with length 4.
• "": Empty string, so length is 0.

Constraints:

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

Approach 1: Brute Force (Naive) for Longest Valid Parentheses

In the brute-force method, we check every possible substring to determine if it forms a valid parentheses substring and then keep track of the maximum length.

Algorithm

1. Generate all possible substrings of the input string.
2. Check if each substring is valid using a helper function.
3. Keep track of the maximum length of valid substrings.

Code Implementation

public class LongestValidParentheses {
    public static int longestValidParentheses(String s) {
        int maxLength = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 2; j <= s.length(); j += 2) {
                if (isValid(s.substring(i, j))) {
                    maxLength = Math.max(maxLength, j - i);
                }
            }
        }
        return maxLength;
    }

    private static boolean isValid(String s) {
        int balance = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                balance++;
            } else {
                balance--;
                if (balance < 0) return false;
            }
        }
        return balance == 0;
    }

    public static void main(String[] args) {
        System.out.println(longestValidParentheses(")()())")); // Output: 4
    }
}

Complexity

• Time Complexity: O(n3), as we generate all substrings and validate each one.
• Space Complexity: O(n) for the stack in the helper function.

Approach 2: Dynamic Programming Approach for Longest Valid Parentheses

Dynamic programming improves upon the brute force approach by avoiding redundant checks. We use an array dp where dp[i] stores the length of the longest valid substring ending at index i.

Algorithm

1. Traverse the string and maintain the dp array.
2. If s[i] == ')', check if there’s a matching '('.
   • Case 1: Matching '(' is immediately before.
   • Case 2: Matching '(' is at a valid substring boundary.
3. Update the maximum length.

Code Implementation

public class LongestValidParentheses {
    public static int longestValidParentheses(String s) {
        int maxLength = 0;
        int[] dp = new int[s.length()];
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1] >= 2) ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxLength = Math.max(maxLength, dp[i]);
            }
        }
        return maxLength;
    }

    public static void main(String[] args) {
        System.out.println(longestValidParentheses(")()())")); // Output: 4
    }
}

Complexity

• Time Complexity: O(n), as we traverse the string once.
• Space Complexity: O(n) for the dp array.

Approach 3: Stack-Based Solution For Longest Valid Parentheses

Using a stack simplifies tracking unmatched parentheses. The stack stores indices of characters, helping compute the length of valid substrings.

Algorithm

1. Push -1 onto the stack to serve as a base index.
2. Traverse the string:
   • If '(', push the index onto the stack.
   • If ')', pop an index and calculate the current valid substring length.
3. Keep track of the maximum length.

Code Implementation

import java.util.Stack;

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

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                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) {
        System.out.println(longestValidParentheses(")()())")); // Output: 4
    }
}

Complexity

• Time Complexity: O(n), as we traverse the string once.
• Space Complexity: O(n) for the stack.

Approach 4: Two-Pointer Traversal for Longest Valid Parentheses

A two-pointer approach eliminates the stack and extra space. We traverse the string twice—once from left to right and once from right to left.

Algorithm

1. Traverse left-to-right, counting open and close parentheses.
   • Reset counts if close > open.
2. Traverse right-to-left, counting close and open parentheses.
   • Reset counts if open > close.

Code Implementation

public class LongestValidParentheses {
    public static int longestValidParentheses(String s) {
        int left = 0, right = 0, maxLength = 0;

        // Left to right
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxLength = Math.max(maxLength, 2 * right);
            } else if (right > left) {
                left = right = 0;
            }
        }

        left = right = 0;

        // Right to left
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == ')') {
                right++;
            } else {
                left++;
            }
            if (left == right) {
                maxLength = Math.max(maxLength, 2 * left);
            } else if (left > right) {
                left = right = 0;
            }
        }

        return maxLength;
    }

    public static void main(String[] args) {
        System.out.println(longestValidParentheses(")()())")); // Output: 4
    }
}

Complexity

• Time Complexity: O(n).
• Space Complexity: O(1).

Conclusion for Longest Valid Parentheses

• Brute Force is a straightforward but inefficient approach.
• Dynamic Programming and Stack-Based methods strike a balance between complexity and efficiency.
• The Two-Pointer method is optimal in terms of space usage.

Choose the approach based on the problem’s constraints and your familiarity with these techniques. Happy coding!