Code Implementation

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = [-1]
        max_len = 0
        for i, ch in enumerate(s):
            if ch == '(':
                stack.append(i)
            else:
                stack.pop()
                if not stack:
                    stack.append(i)
                else:
                    max_len = max(max_len, i - stack[-1])
        return max_len
      

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> stk;
        stk.push(-1);
        int maxLen = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(') {
                stk.push(i);
            } else {
                stk.pop();
                if (stk.empty()) {
                    stk.push(i);
                } else {
                    maxLen = max(maxLen, i - stk.top());
                }
            }
        }
        return maxLen;
    }
};
      

class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int maxLen = 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 {
                    maxLen = Math.max(maxLen, i - stack.peek());
                }
            }
        }
        return maxLen;
    }
}
      

var longestValidParentheses = function(s) {
    let stack = [-1];
    let maxLen = 0;
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') {
            stack.push(i);
        } else {
            stack.pop();
            if (stack.length === 0) {
                stack.push(i);
            } else {
                maxLen = Math.max(maxLen, i - stack[stack.length - 1]);
            }
        }
    }
    return maxLen;
};
      

Problem Description

Given a string s consisting of only the characters '(' and ')', your task is to compute the length of the longest substring that forms a valid set of parentheses. A valid set of parentheses is one where every opening parenthesis '(' has a corresponding closing parenthesis ')' in the correct order and properly nested.

• You must find the length of the longest contiguous substring that is a valid parentheses sequence.
• The input string s can be empty or up to 30,000 characters long.
• Each character in s is either '(' or ')'.

Example: For s = "(()", the answer is 2 because "()" is the longest valid substring.

Thought Process

The problem is essentially about matching parentheses, but not just checking if the whole string is valid; instead, we want the length of the longest valid substring. At first glance, one might consider checking all possible substrings and verifying if each is valid, but this would be extremely inefficient for long strings.

Recognizing that parentheses matching is a classic stack problem, we can use a stack to help us track the positions of unmatched parentheses. When we find a match, we can calculate the length of the current valid substring. Alternatively, we might consider dynamic programming, but the stack approach is often more intuitive and space-efficient for this problem.

The key insight is that by storing indices (not just characters) in the stack, we can easily compute the length of valid substrings when a match is found.

Solution Approach

• Step 1: Initialize a stack with a single value -1. This acts as a "base" for the calculation of lengths and helps handle edge cases where the valid substring starts at the beginning.
• Step 2: Iterate through the string s character by character, tracking the current index i.
• Step 3: If the current character is '(', push its index onto the stack.
• Step 4: If the current character is ')':
  • Pop the top element from the stack (which should be the index of a matching '(' if there is one).
  • If the stack is empty after popping, push the current index as a new base. This means there was no matching '(' for this ')'.
  • If the stack is not empty, calculate the length of the current valid substring as i - stack[-1] (or i - stack.top() in C++/Java). Update the maximum length if this is the largest seen so far.
• Step 5: After iterating through the string, return the maximum length found.

This approach works because the stack always contains indices of unmatched '(' characters, and the base index for the start of the next potential valid substring.

Example Walkthrough

Let's walk through the input s = ")()())" step by step:

1. Initialize: stack = [-1], max_len = 0
2. i = 0, s[0] = ')':
   • Pop -1, stack is now empty.
   • Push 0 as new base, so stack = [0].
3. i = 1, s[1] = '(':
   • Push 1, stack = [0, 1].
4. i = 2, s[2] = ')':
   • Pop 1, stack = [0].
   • Calculate 2 - 0 = 2, update max_len = 2.
5. i = 3, s[3] = '(':
   • Push 3, stack = [0, 3].
6. i = 4, s[4] = ')':
   • Pop 3, stack = [0].
   • Calculate 4 - 0 = 4, update max_len = 4.
7. i = 5, s[5] = ')':
   • Pop 0, stack is now empty.
   • Push 5 as new base, stack = [5].

The longest valid substring is ()() from index 1 to 4, with length 4.

Time and Space Complexity

• Brute-force approach: For each possible substring, check if it is valid. There are O(n²) substrings, and each check takes O(n), so total time is O(n³). This is too slow for large strings.
• Optimized stack approach: We process each character exactly once, and each character is pushed and popped from the stack at most once. So, the time complexity is O(n), where n is the length of the string. The space complexity is O(n) in the worst case (if all characters are '(').

Summary

The key to solving the Longest Valid Parentheses problem efficiently is recognizing the usefulness of a stack for tracking unmatched parentheses and using indices to quickly compute substring lengths. By maintaining a base index and updating the maximum length found at each step, we avoid redundant checks and achieve a linear-time solution. This approach elegantly leverages classic stack mechanics to solve a tricky substring problem in a single pass.