Longest Valid Parenthesis Problem Using Stack

Introduction to Longest Valid Parenthesis Problem Using Stack

The Longest Valid Parenthesis problem involves finding the length of the longest valid (well-formed) parentheses substring. A valid parenthesis substring contains matching pairs of opening and closing parentheses in the correct order. This problem can be efficiently solved using a stack to keep track of indices of parentheses.

---

Step-by-Step Process

Consider a string containing parentheses:

"(()())"

To find the length of the longest valid parentheses substring using a stack, follow these steps:

1. Initialize an Empty Stack: Use a stack to keep track of indices of parentheses.
2. Push Initial Index: Push -1 onto the stack to handle the base case for the first valid substring.
3. Traverse the String: Iterate through each character in the string.
4. Push Opening Parenthesis Index: If the current character is '(', push its index onto the stack.
5. Pop Closing Parenthesis Index: If the current character is ')', pop the top index from the stack. Then, calculate the length of the current valid substring using the difference between the current index and the new top index of the stack. Update the maximum length if the current length is greater.
6. Push Current Index if Stack is Empty: If the stack becomes empty after popping, push the current index onto the stack to serve as the base for the next valid substring.

After performing these steps, the length of the longest valid parentheses substring will be found.

Input: "(()())"
Output: 6

---

Detailed Example Steps

Consider the input string "(()())". We want to find the length of the longest valid parentheses substring.

1. Initialize an Empty Stack: Stack = []
2. Push Initial Index: Stack = [-1]
3. Traverse the String:
• Current Character: '(', Index: 0, Stack = [-1, 0]
• Current Character: '(', Index: 1, Stack = [-1, 0, 1]
• Current Character: ')', Index: 2, Stack = [-1, 0] (Pop 1, Current Length = 2 - 0 = 2, Max Length = 2)
• Current Character: '(', Index: 3, Stack = [-1, 0, 3]
• Current Character: ')', Index: 4, Stack = [-1, 0] (Pop 3, Current Length = 4 - 0 = 4, Max Length = 4)
• Current Character: ')', Index: 5, Stack = [-1] (Pop 0, Current Length = 5 - (-1) = 6, Max Length = 6)
4. Final Result: The maximum length of the valid parentheses substring is 6.

---

Pseudo Code

Function longest_valid_parentheses(s):
    # Initialize an empty stack and push -1 onto it
    stack = [-1]
    max_length = 0
    # Traverse the string
    For i in range(len(s)):
        If s[i] == '(':  # Push index of '(' onto the stack
            stack.append(i)
        Else:  # Pop the top index for ')'
            stack.pop()
            If stack:  # Calculate the length of the current valid substring
                max_length = max(max_length, i - stack[-1])
            Else:  # Push the current index onto the stack if it becomes empty
                stack.append(i)
    Return max_length

---

Python Program to Solve the Longest Valid Parentheses Problem Using Stack

def longest_valid_parentheses(s):
    # Initialize an empty stack and push -1 onto it
    stack = [-1]
    max_length = 0
    # Traverse the string
    for i in range(len(s)):
        if s[i] == '(':  # Push index of '(' onto the stack
            stack.append(i)
        else:  # Pop the top index for ')'
            stack.pop()
            if stack:  # Calculate the length of the current valid substring
                max_length = max(max_length, i - stack[-1])
            else:  # Push the current index onto the stack if it becomes empty
                stack.append(i)
    return max_length

# Example usage:
input_string = "(()())"
print(f"Input string: {input_string}")  # Output: Input string: (()())
result = longest_valid_parentheses(input_string)
print(f"Longest valid parentheses length: {result}")  # Output: Longest valid parentheses length: 6

This Python program defines a function longest_valid_parentheses that uses a stack to find the length of the longest valid parentheses substring. The function iterates through the string, uses the stack to keep track of indices of parentheses, and calculates the maximum length of valid parentheses substrings.