Longest Valid Parentheses

Longest Valid Parentheses - Uber Coding Interview | ShowOffer

You are given a string containing just the characters '(' and ')'. Your task is to find the length of the longest valid (well-formed) parentheses substring.

Constraints:

• The input consists only of '(' and ')'.
• The string length is between 1 and 1000.

Examples:

1. Input: ((()))) Output: 2 Explanation: The longest valid parentheses substring is (), which has a length of 2.

2. Input: ((())) Output: 2 Explanation: The longest valid parentheses substring is (), which has a length of 2.

3. Input: )()() Output: 4 Explanation: The longest valid parentheses substring is ()(), which has a length of 4.

Hints:

1. Use a stack to keep track of the indices of the characters in the string.
2. When you encounter a ')', check if the top of the stack is a '('. If it is, pop the stack and calculate the length of the valid substring.
3. If the top of the stack is not a '(', push the current index onto the stack.

Solution: `python class Solution: def longestValidParentheses(self, s: str) -> int: max_len = 0 stack = [-1] # Initialize stack with -1 to handle edge cases

    for i, char in enumerate(s):
        if char == '(':
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)
            else:
                max_len = max(max_len, i - stack[-1])

    return max_len

`

Explanation:

• We use a stack to keep track of the indices of the characters in the string.
• When we encounter a '(', we push its index onto the stack.
• When we encounter a ')', we pop the top index from the stack. If the stack is empty after popping, we push the current index onto the stack.
• If the stack is not empty after popping, we calculate the length of the valid substring by subtracting the top index from the current index and update the maximum length if necessary.

This solution has a time complexity of O(n) and a space complexity of O(n), where n is the length of the input string.