Longest Valid Parentheses - Leetcode Solution

Problem Description:

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

Example: Input: "(()" Output: 2 Explanation: The longest valid parentheses substring is "()"

Input: ")()())" Output: 4 Explanation: The longest valid parentheses substring is "()()"

Solution:

We can use dynamic programming to solve this problem. Let us define dp[i] as the length of the longest valid parentheses substring ending at index i in the given string.

To compute dp[i], we need to analyze the substring ending at index i. There are two cases:

1. If the substring ends with '(', then dp[i] must be 0, since no valid parentheses substring can end with '('.

2. If the substring ends with ')' we need to consider its corresponding '(' in the string. Let 'j' be the index of the matching opening bracket for the closing bracket at index 'i'. Then, we have two cases:

   a. If j-1 >= 0, then dp[i] = dp[j-1] + 2, because the substring from j to i is a valid parenthese substring and we can also add the length of the valid subsequence ending at index j-1.

   b. If j-1 < 0, then dp[i] = 2, because the first two characters of the given string form a valid parentheses substring (i.e "()").

We can find the matching opening bracket for a given closing bracket in constant time using a stack. We push the index of the opening bracket onto the stack when we encounter it and pop the last element when we encounter a closing bracket.

The final answer is the maximum element in the dp array.

Pseudo-code for the algorithm:

1. Initialize an empty stack and a dp array of length n with all values as 0.
2. For i = 0 to n-1: a. If s[i] = '(', push i onto the stack. b. If s[i] = ')' and stack is not empty, pop the top element. i. If stack is empty, dp[i] = i+1, otherwise dp[i] = (i - stack.top()) c. Update the maximum length seen so far and update dp array.
3. Return maximum length seen so far.

Time Complexity: O(n), where n is the length of the given string s.

Space Complexity: O(n), where n is the length of the given string s.

Code in Python:

class Solution: def longestValidParentheses(self, s: str) -> int: stack = [-1] max_len = 0 n = len(s) dp = [0] * n for i in range(n): if s[i] == '(': stack.append(i) else: if stack and s[stack[-1]] == '(': stack.pop() if not stack: dp[i] = i+1 else: dp[i] = i - stack[-1] max_len = max(max_len, dp[i]) else: stack.append(i) return max_len

1