π‘ Problem Formulation: Given a string containing just the characters ‘(
‘ and ‘)
‘, the goal is to find the length of the longest well-formed (valid) parentheses substring. For example, given the input ‘()()
‘, the desired output is ‘4
‘, whereas for ‘(())
‘, the output should also be ‘4
‘.
Method 1: Stack-Based Approach
The Stack-Based Approach involves using a stack to keep track of the indices of parentheses. This method pushes indices onto the stack when an opening parenthesis is encountered and pops when a closing parenthesis that forms a valid pair is found. The length of the longest valid parenthesis is determined by the distance between invalid parentheses or the base of the stack.
Here’s an example:
def longestValidParentheses(s): stack = [-1] max_length = 0 for i in range(len(s)): if s[i] == '(': stack.append(i) else: stack.pop() if len(stack) == 0: stack.append(i) else: max_length = max(max_length, i - stack[-1]) return max_length print(longestValidParentheses(")()())"))
Output: 4
This snippet defines a function longestValidParentheses
that takes a string as input and initializes a stack with ‘-1
‘ to act as a base for the first valid string. It iterates through the string, updating the maximum length whenever valid parentheses are closed. When the stack is empty, it means an unmatched closing parenthesis was found, warranting a new base index.
Method 2: Dynamic Programming
Dynamic Programming solves problems by combining the solutions of subproblems. This method uses an array to store the lengths of the valid substrings at each index and builds upon them to find the maximum length. It only needs a single pass through the string and is efficient in terms of time complexity.
Here’s an example:
def longestValidParentheses(s): dp = [0] * (len(s) + 1) max_length = 0 for i in range(1, len(s)): if s[i] == ')': if s[i-1] == '(': dp[i] = dp[i-2] + 2 elif i - dp[i-1] > 0 and s[i - dp[i-1] - 1] == '(': dp[i] = dp[i-1] + dp[i - dp[i-1] - 2] + 2 max_length = max(max_length, dp[i]) return max_length print(longestValidParentheses("((()))"))
Output: 6
The function longestValidParentheses
utilizes a dynamic programming table (array dp
) to record the lengths of the valid parentheses at each index. The table is updated based on the surrounding characters and the previously computed values. The longest length is continuously updated and eventually returned.
Method 3: Two Pointer Technique
The Two Pointer Technique uses two counters that traverse the string twice: once from left to right, and then from right to left. The first pass counts matching pairs from the start, and the second pass counts matches from the end, catering to cases where one direction might fail to achieve valid pairs.
Here’s an example:
def longestValidParentheses(s): left = right = max_length = 0 for i in s: if i == '(': 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 i in reversed(s): if i == '(': left += 1 else: right += 1 if left == right: max_length = max(max_length, 2 * left) elif left > right: left = right = 0 return max_length print(longestValidParentheses("(()"))
Output: 2
In this code, the function longestValidParentheses
employs the two-pointer approach to count the number of valid pairs both in the forward and backward directions, resetting if parentheses are mismatched in either direction. The maximum length of valid parentheses is computed accordingly.
Method 4: Regular Expression Matching
For a simpler, albeit less efficient method, we can use regular expressions. This involves iteratively removing matched pairs of parentheses from the string with a pattern and calculating the length of the resulting valid substrings. However, performance with large strings may be an issue due to the method’s recursive nature.
Here’s an example:
import re def longestValidParentheses(s): pattern = re.compile(r'\(\)') while True: s_new = pattern.sub('', s) if s == s_new: break s = s_new return len(s) print(longestValidParentheses("(()())"))
Output: 6
This code repeats the removal of valid parenthesis pairs ‘()
‘ from the string using regular expressions until no more such pairs can be found. The length of the string after all removals gives the length of the longest set of valid parentheses.
Bonus One-Liner Method 5: Functional Approach
This elegant yet less readable one-liner uses a combination of functional programming techniques, including reduce
, lambda expressions, and list comprehension, to compute the result in a single expression.
Here’s an example:
from functools import reduce print(reduce(lambda acc, val: (acc[0], acc[1] + val, max(acc[2], acc[1])), [(1 if c == ')' else -1) for c in "(()())"], (0, 0, 0))[2])
Output: 6
This one-liner uses reduce
to accumulate and track the balance and maximum length of valid parentheses while iterating through the input string, checkmarked by ‘(
‘ increasing the balance and ‘)
‘ decreasing it. Despite its brevity, this method sacrifices readability for conciseness.
Summary/Discussion
- Method 1: Stack-Based Approach. Efficient for complex strings. Requires additional space for the stack.
- Method 2: Dynamic Programming. Suitable for inputs that benefit from precomputed sub-solutions. Can be more space-intensive with larger strings.
- Method 3: Two Pointer Technique. Memory-efficient and straightforward. Can require two passes through the string.
- Method 4: Regular Expression Matching. Simpler code for smaller strings. Potentially poor performance on large strings and complex scenarios.
- Method 5: Functional Approach. A one-line solution that is elegant but can be difficult to understand and debug.