We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Valid Parentheses

Number: 32

Difficulty: Hard

Paid? No

Companies: Amazon, Google, Microsoft, Meta, InMobi, MakeMyTrip, Zoho, Bloomberg, Uber, Zeta, Apple, TikTok, Adobe, Oracle, Salesforce, Walmart Labs, Morgan Stanley, DE Shaw

Problem Description

Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.

Key Insights

  • Use a stack to keep track of indices where potential valid substrings begin.
  • Start by pushing a dummy index (-1) to handle edge cases.
  • For every '(', push its index onto the stack.
  • For every ')', pop from the stack. If the stack becomes empty, push the current index as a new base. Otherwise, compute the length of the valid substring using the current index minus the top index of the stack.
  • An alternative is the dynamic programming approach where dp[i] represents the length of the longest valid substring ending at index i.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the string. Space Complexity: O(n) for the stack data structure.

Solution

The stack-based solution works by maintaining indices for unmatched parentheses. Initially, a dummy index (-1) is pushed onto the stack to serve as the base for calculating subsequent valid substring lengths. As we iterate through the string:

  • If the character is '(', we push its index onto the stack.
  • If the character is ')', we pop from the stack. If the stack is empty afterwards, that means there is no valid starting position, so we push the current index to reset the base. Otherwise, we calculate the length of the current valid substring by subtracting the current index with the new top index of the stack and update the maximum length accordingly.

Code Solutions

# Python solution using a stack
def longestValidParentheses(s: str) -> int:
    # Initialize the stack with the base index -1
    stack = [-1]
    max_length = 0

    # Iterate over the string with index
    for i, char in enumerate(s):
        if char == '(':
            # Push the index of '(' onto the stack
            stack.append(i)
        else:
            # Pop the last index for ')'
            stack.pop()
            if not stack:
                # If stack is empty, push current index as the new base
                stack.append(i)
            else:
                # Calculate the length of the current valid substring
                current_length = i - stack[-1]
                max_length = max(max_length, current_length)

    return max_length

# Example usage:
print(longestValidParentheses(")()())"))  # Output: 4
← Back to All Questions