32. Longest Valid Parentheses


Problem Description

In this problem, we are given a string that consists only of the characters '(' and ')'. The goal is to find the length of the longest substring that represents a valid sequence of parentheses. A valid parentheses string is one where every '(' has a matching ')' and the pairs are well-nested. For example, in the string "(()", only the substring "()" is valid and has a length of 2.

Intuition

The key to solving this problem lies in the fact that a valid parentheses string must end with a ')' character. To systematically approach this, we use dynamic programming (DP). The solution builds up information about the substrings ending at each position in the input string, using an array (or list) to record the results.

The intuition behind the dynamic programming solution is this: We define a DP array where the ith entry, f[i], represents the length of the longest valid parentheses substring ending at the index i - 1 in the input string. To fill in this array, we consider two main cases:

  1. If the character at position i - 1 is '(', then no valid substring can end with this character, so f[i] would be 0.

  2. If the character at position i - 1 is ')', this is where it gets interesting. We look at two possible scenarios:

    a. If the character right before it (at i - 2) is '(', we have a pair "()", so the length of the longest valid substring ending at i - 1 would be f[i - 2] + 2, since we're adding these two characters to whatever we had before.

    b. If the character at i - 2 is also ')', the situation is a bit more complex. This might be a continuation of a previously started valid string. We first check that there's a valid string ending just before the current one (at i - f[i - 1] - 2). If there is, and the character at the beginning of this string (at i - f[i - 1] - 2) is '(', then the current ')' can close this, forming a new valid string, so we append the lengths: f[i - 1] + 2 + f[i - f[i - 1] - 2].

With this DP array filled out, all we need to do is to find the maximum value in it, which represents the length of the longest valid parentheses substring in the entire input string. The code iterates through the string only once and fills the DP array as it goes, making it an efficient solution.

Learn more about Stack and Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Solution Approach

The solution presented here is a prime example of dynamic programming. Specifically, it showcases a bottom-up iterative approach to solve the problem of finding the longest valid parentheses substring. Here's how the approach is implemented:

Firstly, we initialize a list f with a length of n + 1, where n is the length of the input string s, and fill it with zeros. This list will hold our dynamic programming table, where f[i] represents the length of the longest valid parentheses substring that ends at index i - 1.

As we iterate over the string (1-indexed for easy reference), we only need to consider elements in s that are closing parentheses ')'. This is because valid substrings can only end with a closing parenthesis.

For each closing parenthesis at index i, we have two main cases:

  • Case 1: The previous character is an opening parenthesis '('. This means we've found a simple pair of parentheses "()". The length of the longest valid substring ending at i is f[i - 2] + 2. This consists of the length of whatever valid substring ends right before this pair plus the length of this pair (2).

  • Case 2: The previous character is also a closing parenthesis ')'. Here, we have to look back and check if there's a matching opening parenthesis that can pair with our current one. To find it, we subtract the length of the valid substring ending just before (at f[i - 1]) from i and go back one more step (hence i - f[i - 1] - 2). If we find that there's an opening parenthesis at that position, we can extend the length of the valid substring ending there by adding the length of the valid substring ending at our current position plus 2 for the current pair "()", and also add the value at f[j - 1], where j is the index we just found to check availability of a valid opening parenthesis. This step accounts for concatenating a new valid pair to an existing valid substring.

By repeatedly applying the above logic as we scan through the string, we build up our DP table. Once we have processed the entire string, we can simply return max(f), which will give us the length of the longest valid parentheses substring found.

The approach effectively breaks down the problem into manageable subproblems. It ensures that every position in the string is only calculated once, giving us an overall time complexity of O(n) where n is the length of the string. The space complexity is also O(n) due to the additional list used for storing the lengths of longest valid substrings.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which type of traversal does breadth first search do?

Example Walkthrough

Let's apply the solution approach to a small example and illustrate how it works.

Suppose we are given the string s = "(()())".

We first initialize a list f with a length of n + 1 = 7 (since the length of s is 6), and fill it with zeros: f = [0, 0, 0, 0, 0, 0, 0].

Now, we will iterate over the string, starting from index 1:

  1. i = 1: s[i - 1] = '(', so we do nothing because a valid substring cannot end with '('. f = [0, 0, 0, 0, 0, 0, 0]

  2. i = 2: s[i - 1] = '(', we do nothing again for the same reason. f = [0, 0, 0, 0, 0, 0, 0]

  3. i = 3: s[i - 1] = ')', previous char is '(', so we have "()", and f[i] = f[1] + 2 = 2. f = [0, 0, 2, 0, 0, 0, 0]

  4. i = 4: s[i - 1] = '(', do nothing. f = [0, 0, 2, 0, 0, 0, 0]

  5. i = 5: s[i - 1] = ')', the previous character is '(', so "()" again, f[i] = f[3] + 2 = 4 (because we are adding the pair () to what we had at f[3]). f = [0, 0, 2, 0, 4, 0, 0]

  6. i = 6: s[i - 1] = ')', the previous character is ')', we check i - f[i - 1] - 2 = 6 - 4 - 2 = 0, at position 0 we have '(', so we have a longer valid substring that spans the whole current string, f[i] = f[4] + 2 + f[6 - 4 - 2] = 4 + 2 + 0. f = [0, 0, 2, 0, 4, 0, 6]

Now our DP list f tells us that the longest valid substring ending at any position in s. The max value in f is 6, which is the length of the longest valid parentheses substring in s.

This walkthrough demonstrates the bottom-up DP technique used to find the longest valid parentheses substring in linear time complexity, which is O(n).

Solution Implementation

1class Solution:
2    def longestValidParentheses(self, s: str) -> int:
3        # Get the length of the input string
4        string_length = len(s)
5        # Initialize a DP array with zeros, one extra for the base case
6        dp = [0] * (string_length + 1)
7      
8        # Loop over the characters of string starting from index 1 for convenience
9        for index, char in enumerate(s, 1):
10            # We look for closing parentheses, as they mark possible ends of valid substrings
11            if char == ")":
12                # If the previous char is '(', it's a pair "()"
13                if index > 1 and s[index - 2] == "(":
14                    # Add 2 to the result two positions ago in dp array
15                    dp[index] = dp[index - 2] + 2
16                else:
17                    # Get the index of the potential matching '('
18                    match_index = index - dp[index - 1] - 1
19                    # Make sure match_index is within bounds and check for '('
20                    if match_index > 0 and s[match_index - 1] == "(":
21                        # Add the length of the valid substring ending right before the current one,
22                        # plus two for the '()' just found, plus length of valid substring before the pair
23                        dp[index] = dp[index - 1] + 2 + dp[match_index - 1]
24      
25        # Return the maximum length of valid parentheses found
26        return max(dp)
27
1class Solution {
2    public int longestValidParentheses(String s) {
3        int strLength = s.length();
4        int[] validLengths = new int[strLength + 1]; // Array to store the length of valid parentheses substrings at each index.
5        int maxValidLength = 0; // The maximum length of valid parentheses found.
6
7        // Iterate starting from the second character as we need to check pairs.
8        for (int i = 2; i <= strLength; ++i) {
9            // Check if the current character is a closing parenthesis.
10            if (s.charAt(i - 1) == ')') {
11                // If the previous character is an opening parenthesis, it forms a valid pair.
12                if (s.charAt(i - 2) == '(') {
13                    validLengths[i] = validLengths[i - 2] + 2; // Add 2 for the valid '()' pair.
14                } else {
15                    // If the previous character is also a closing parenthesis,
16                    // find the position before the valid substring that starts
17                    // just before the current one.
18                    int prevIndex = i - validLengths[i - 1] - 1;
19                    // Check if there's a matching opening parenthesis.
20                    if (prevIndex > 0 && s.charAt(prevIndex - 1) == '(') {
21                        validLengths[i] = validLengths[i - 1] + 2 + validLengths[prevIndex - 1]; // Add lengths of valid substrings plus the new pair.
22                    }
23                }
24                // Update the maximum length if needed.
25                maxValidLength = Math.max(maxValidLength, validLengths[i]);
26            }
27        }
28
29        return maxValidLength; // Return the maximum length of valid parentheses.
30    }
31}
32
1#include <vector>
2#include <algorithm>
3#include <cstring>
4
5class Solution {
6public:
7    int longestValidParentheses(string s) {
8        int length = s.size();
9
10        // Create a dynamic programming vector with 0 initialization
11        vector<int> dp(length + 1, 0);
12
13        // Iterate over the string, starting at the second character
14        for (int i = 2; i <= length; ++i) {
15            // If the current character is a closing parenthesis
16            if (s[i - 1] == ')') {
17                // If the previous character is an opening parenthesis
18                if (s[i - 2] == '(') {
19                    // Add 2 to the dynamic programming array at position i
20                    // This forms a pair with the previous '('
21                    dp[i] = dp[i - 2] + 2;
22                } else {
23                    // Calculate the index before the previous valid substring
24                    int previousIndex = i - dp[i - 1] - 1;
25                    // If there's an opening parenthesis before the previous valid substring
26                    if (previousIndex > 0 && s[previousIndex - 1] == '(') {
27                        // Add the lengths of the currently found valid substring, the one before it,
28                        // and the one before the opening parenthesis
29                        dp[i] = dp[i - 1] + 2 + dp[previousIndex - 1];
30                    }
31                }
32            }
33        }
34
35        // Return the maximum length found in the dp array
36        return *max_element(dp.begin(), dp.end());
37    }
38};
39
1// This function calculates the length of the longest valid (well-formed) parentheses substring.
2function longestValidParentheses(s: string): number {
3    const lengthOfString: number = s.length;
4    // Initialize an array to record the length of the longest valid parentheses ending at each position.
5    const dp: number[] = new Array(lengthOfString + 1).fill(0);
6    let maxValidLength: number = 0; // Keep track of the maximum valid length.
7
8    // Iterate through the string starting from the second character position.
9    for (let i = 2; i <= lengthOfString; i++) {
10        // Check if the current character is a closing parenthesis.
11        if (s[i - 1] === ')') {
12            // If previous character is an opening parenthesis, it's a valid pair.
13            if (s[i - 2] === '(') {
14                dp[i] = dp[i - 2] + 2;
15            } else {
16                // Check if the substring before the last valid parentheses is an opening parenthesis.
17                const previousIndex: number = i - dp[i - 1] - 1;
18                if (previousIndex > 0 && s[previousIndex - 1] === '(') {
19                    dp[i] = dp[i - 1] + 2 + dp[previousIndex - 1];
20                }
21            }
22        }
23        // Update the maximum valid length found so far.
24        maxValidLength = Math.max(maxValidLength, dp[i]);
25    }
26
27    // Return the maximum valid length of the parentheses found.
28    return maxValidLength;
29}
30
Not Sure What to Study? Take the 2-min Quiz:

Which of the following uses divide and conquer strategy?

Time and Space Complexity

The time complexity of the given code is O(n) where n is the length of the string s. This is because the algorithm iterates through all characters of the input string once, and for each character, it performs a constant amount of work.

The space complexity of the code is O(n) as well, due to the auxiliary space used by the list f, which has a length of n + 1. Each element of the list f stores the length of the longest valid substring ending at that position, thereby requiring linear space relative to the input string length.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Depth first search is equivalent to which of the tree traversal order?


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫