Longest Valid Parentheses - Python Solution

1. Introduction

"Longest Valid Parentheses" is a compelling problem in string manipulation and stack-based algorithms. It focuses on finding the maximum length of a well-formed parentheses substring in a given string. This problem is significant for understanding stack operations and string processing techniques, and is commonly encountered in coding interviews.

Problem

Given a string containing just the characters '(' and ')', the task is to return the length of the longest valid (well-formed) parentheses substring. A valid parentheses substring is one where each opening parenthesis '(' is matched with a corresponding closing parenthesis ')'.

2. Solution Steps

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

2. Initialize the stack with a base value to handle edge cases.

3. Iterate through each character in the string.

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

5. If a closing parenthesis is encountered, pop the top of the stack.

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

7. Calculate the length of the valid substring using the current index and the top of the stack.

8. Update the maximum length if a longer valid substring is found.

3. Code Program

def longestValidParentheses(s):
    maxLen = 0
    stack = [-1]  # Initialize stack with base index

    for i in range(len(s)):
        if s[i] == '(':
            stack.append(i)  # Push index of '(' onto the stack
        else:
            stack.pop()  # Pop for ')'
            if not stack:
                stack.append(i)  # Reset stack base index
            else:
                maxLen = max(maxLen, i - stack[-1])  # Update max length

    return maxLen

# Example Usage
print(longestValidParentheses("(()"))
print(longestValidParentheses(")()())"))

Output:

2
4

Explanation:

1. Stack Utilization: A stack is used to track indices of '(' characters and to help identify valid substrings.

2. Iterative Processing: The string is processed character by character to identify valid parentheses substrings.

3. Opening Parenthesis Handling: Indices of '(' characters are pushed onto the stack.

4. Closing Parenthesis Handling: For each ')', the stack is popped, and the length of the valid substring is calculated.

5. Empty Stack Case: If the stack is empty after a pop, the current index is pushed to reset the base index.

6. Maximum Length Calculation: The length of each valid substring is compared with the current maximum length to find the longest valid substring.