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.
Consider a string containing parentheses:
"(()())"
To find the length of the longest valid parentheses substring using a stack, follow these steps:
After performing these steps, the length of the longest valid parentheses substring will be found.
Input: "(()())"
Output: 6
Consider the input string "(()())". We want to find the length of the longest valid parentheses substring.
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
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.