Introduction

In this blog post, we will explore how to solve the LeetCode problem "32" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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 ')'.

Explanation

Here's the breakdown of the approach and the Python code:

• High-Level Approach:

  • Stack-based tracking: Use a stack to keep track of the indices of open parentheses.
  • Matching parentheses: When a closing parenthesis is encountered, check if the stack is empty. If not, pop the top of the stack (matching open parenthesis).
  • Calculating length: The length of the valid substring is determined by the difference between the current index and the top of the stack (or -1 if the stack is empty).

• Complexity:

  • Runtime: O(n), where n is the length of the string.
  • Storage: O(n) in the worst case (e.g., "(((((").

Code

    def longestValidParentheses(s: str) -> int:
    """
    Finds the length of the longest valid (well-formed) parentheses substring.

    Args:
        s: The input string containing only '(' and ')'.

    Returns:
        The length of the longest valid parentheses substring.
    """

    max_len = 0
    stack = [-1]  # Initialize stack with -1 to handle cases where the first char is ')'

    for i, char in enumerate(s):
        if char == '(':
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)  # If stack is empty, push the current index
            else:
                max_len = max(max_len, i - stack[-1])  # Calculate length

    return max_len