# Solving Leetcode Interviews in Seconds with AI: Longest Valid Parentheses


	# 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](https://www.chatmagic.app), 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
	```python
	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
	```