Longest Valid Parentheses

Given a string str consisting of opening and closing parenthesis ‘(‘ and ‘)‘. Find length of the longest valid parenthesis substring.

A parenthesis string is valid if:

• For every opening parenthesis, there is a closing parenthesis.
• Opening parenthesis must be closed in the correct order.

Examples :

Input: str = ((()
Output: 2
Explaination: The longest valid parenthesis substring is "()".

Input: str = )()())
Output: 4
Explaination: The longest valid parenthesis substring is "()()".

Expected Time Complexity: O(|str|)
Expected Auxiliary Space: O(|str|)

Constraints:
1 ≤ |str| ≤ 10⁵

Approach 01:

class Solution {
public:
    int maxLength(string str) {
        int length = str.size();
        int maxLength = 0;
        stack<int> indexStack; // Stack to keep track of indices of unmatched opening parentheses
        stack<int> tempStack;  // Stack to track the indices of the current valid substring

        for (int i = 0; i < length; ++i) {
            if (!indexStack.empty() && str[indexStack.top()] == '(' && str[i] == ')') {
                indexStack.pop();
                tempStack.pop();
                // If tempStack is empty, calculate the length from the start
                // Otherwise, calculate the length from the index on the top of tempStack
                maxLength = tempStack.empty() ? i + 1 : max(maxLength, i - tempStack.top());
            } else {
                tempStack.push(i);
                indexStack.push(i);
            }
        }
        
        return maxLength;
    }
};

class Solution:
    def maxLength(self, s: str) -> int:
        length = len(s)
        maxLength = 0
        indexStack = []  # Stack to keep track of indices of unmatched opening parentheses
        tempStack = []   # Stack to track the indices of the current valid substring

        for i in range(length):
            if indexStack and s[indexStack[-1]] == '(' and s[i] == ')':
                indexStack.pop()
                tempStack.pop()
                # If tempStack is empty, calculate the length from the start
                # Otherwise, calculate the length from the index on the top of tempStack
                maxLength = i + 1 if not tempStack else max(maxLength, i - tempStack[-1])
            else:
                tempStack.append(i)
                indexStack.append(i)
        
        return maxLength

Time Complexity

• Iterating Through the String:

  The algorithm makes a single pass through the input string str, which has a length of n. Each character is processed once, making this operation \(O(n)\).

• Stack Operations:

  Each character is pushed and popped from the stacks at most once. Stack operations (push and pop) are \(O(1)\) operations. Since there are two stacks and each character is pushed and popped only once, the operations are still \(O(n)\) in total.

• Overall Time Complexity:

  The overall time complexity is \(O(n)\), where n is the length of the input string str.

Space Complexity

• Space for Stacks:

  Two stacks are used: indexStack and tempStack. In the worst case, both stacks can grow to hold all the indices of the string, which is \(O(n)\).

• Space for Variables:

  Additional variables such as length and maxLength use constant space, \(O(1)\).

• Overall Space Complexity:

  The overall space complexity is \(O(n)\), due to the space required for the stacks.