Given a string consisting of opening and closing parenthesis (let moonparenthesis only), find the length of the longest valid parenthesis sub-string

To find the length of the longest valid parenthesis sub-string in a given string, we can use a stack data structure.

1. Initialize an empty stack and a variable called maxLength to keep track of the maximum length of valid parenthesis sub-string found so far.

2. Iterate through each character in the given string.

3. If the current character is an opening parenthesis (i.e., '('), push its index onto the stack.

4. If the current character is a closing parenthesis (i.e., ')'), check if the stack is empty or the top element of the stack is also a closing parenthesis. If either condition is true, push the index of the current closing parenthesis onto the stack.

5. If the current character is a closing parenthesis and the top element of the stack is an opening parenthesis, it means we have found a valid parenthesis sub-string. Pop the top element from the stack and calculate the length of the valid sub-string by subtracting the index of the popped element from the current index. Update the maxLength if necessary.

6. After iterating through all the characters, the stack may still contain indices of unmatched opening parentheses. To handle this, we can use the indices in the stack to calculate the lengths of any remaining valid sub-strings and update the maxLength accordingly.

7. Finally, return the maxLength as the length of the longest valid parenthesis sub-string in the given string.

Note: This solution has a time complexity of O(n), where n is the length of the given string.