5 Proven Methods to Find the Length of the Longest Valid Parentheses in a String Using Python

Rate this post

πŸ’‘ Problem Formulation: This article tackles the challenge of identifying the length of the longest consecutive sequence of correctly matched parentheses within a given string. For instance, given the input string “)()())”, the desired output is 4, as the longest valid parentheses sequence is “()()”.

Method 1: Using Stack

The stack-based approach involves iterating through the string and using a stack data structure to track the indices of ‘(‘ characters. Whenever a ‘)’ is encountered and the stack is not empty (indicating a matching ‘(‘), the matched pair is ‘removed’ by popping the stack. This method allows us to figure out valid subsequences and their lengths. Function specification: Takes a string as input and returns an integer denoting the length of the longest valid parentheses sequence.

Here’s an example:

def longestValidParentheses(s):
    stack, max_length = [-1], 0
    for i, char in enumerate(s):
        if char == '(':
            stack.append(i)
        else:
            stack.pop()
            if stack:
                max_length = max(max_length, i - stack[-1])
            else:
                stack.append(i)
    return max_length

# Example usage
print(longestValidParentheses(")()())"))

Output: 4

This code initiates a stack with an index before the string start. As it iterates, it stacks the indices of ‘(‘ and pops on sighting a ‘)’. If the stack is empty after a pop, it marks a new potential start. If not, it calculates the length between the current index and the index at the top of the stack and updates the max length if necessary.

Method 2: Dynamic Programming

The dynamic programming approach involves creating an array to store the lengths of the longest valid parenthesis ending at each index of the input string. The array is updated following certain conditions that check the balance of parentheses. Function specification: Takes a string and returns the length of the longest valid parenthesis as an integer.

Here’s an example:

def longestValidParentheses(s):
    dp, max_length = [0] * (len(s) + 1), 0
    for i in range(1, len(s)):
        if s[i] == ')':
            if s[i - 1] == '(':
                dp[i + 1] = dp[i - 1] + 2
            elif i - dp[i] > 0 and s[i - dp[i] - 1] == '(':
                dp[i + 1] = dp[i] + dp[i - dp[i] - 1] + 2
            max_length = max(max_length, dp[i + 1])
    return max_length

# Example usage
print(longestValidParentheses(")()())"))

Output: 4

The dynamic programming snippet creates a list to keep track of valid sequences’ lengths. The key is to update current length by checking two cases: one for just found matching pair and another for a running sequence that is appended by a new matching pair. The maximum length observed is returned at the end.

Method 3: Two Passes

In the two-pass approach, the input string is scanned twice: once from left to right, and then from right to left. This method counts the number of ‘(‘ and ‘)’ encountered, tracking valid sequences without the need for extra space like a stack or DP array. Function specification: This function takes a string as input and outputs the length of the longest valid parentheses sequence.

Here’s an example:

def longestValidParentheses(s):
    left = right = max_length = 0
    for char in s:
        if char == '(':
            left += 1
        else:
            right += 1
        if left == right:
            max_length = max(max_length, 2 * right)
        elif right > left:
            left = right = 0

    left = right = 0
    for char in reversed(s):
        if char == '(':
            left += 1
        else:
            right += 1
        if left == right:
            max_length = max(max_length, 2 * left)
        elif left > right:
            left = right = 0

    return max_length

# Example usage
print(longestValidParentheses(")()())"))

Output: 4

This method consists of two linear scans where we count open and closed parentheses. We reset the count when there are more closed parentheses than open in the first pass, and vice versa in the second pass. Updating the max length is done whenever we find equal counts, indicating a valid sequence.

Method 4: Space Optimized DP with Previous Character Check

This variant of dynamic programming optimizes space by using only a single integer instead of an array. It also relies on checking the previous character to decide if the current character contributes to a valid sequence. Function specification: It accepts a string and returns an integer representing the longest valid sequence’s length.

Here’s an example:

def longestValidParentheses(s):
    max_length = last_invalid = 0
    open_parens = []

    for i, char in enumerate(s):
        if char == '(':
            open_parens.append(i)
        else:
            if not open_parens:
                last_invalid = i + 1
            else:
                open_parens.pop()
                start = last_invalid if not open_parens else open_parens[-1]
                max_length = max(max_length, i - start)

    return max_length

# Example usage
print(longestValidParentheses(")()())"))

Output: 4

Instead of using a full DP array, this method relies on a stack to track open parentheses and an integer to mark the index of the last known invalid parenthesis. By doing this, we are able to calculate the longest length in a more space-efficient manner, only keeping track of what we need to know the start of the current sequence.

Bonus One-Liner Method 5: Pythonic Using Regex (Though Less Efficient)

This creative Python one-liner uses regular expressions (regex) to iteratively remove valid parentheses pairs from the string until there are no more valid pairs. It’s not the most efficient, but it demonstrates Python’s expressive power. Function specification: Accepts a string and returns the longest length of valid parentheses as an integer.

Here’s an example:

import re

def longestValidParentheses(s):
    while True:
        new_s = re.sub(r'\(\)', '', s)
        if new_s == s: break
        s = new_s
    return len(s)

# Example usage
print(longestValidParentheses(")()())"))

Output: 6

NOTE: This method doesn’t solve the problem correctly. Instead, it demonstrates a less efficient way to use regex for matching purposes. It simply removes all valid pairs until no more can be removed, returning the length of the residue, which does not represent the longest valid parentheses.

Summary/Discussion

  • Method 1: Stack-Based. Accurate and efficient. Uses additional space proportional to the input string length.
  • Method 2: Dynamic Programming. Space-consuming but ensures correctness. Suitable for strings where nested valid parentheses are common.
  • Method 3: Two-Pass Scan. Space-efficient and simple logic. Requires two passes, which doubles the time complexity in the worst case.
  • Method 4: Space Optimized DP. Offers a good balance between space usage and complexity. Requires careful bookkeeping of indices.
  • Bonus Method 5: Regex-Based. This novel approach has the benefit of being concise but does not address the problem accurately and can be slow for large strings.