Leetcode 32 Solution

Leetcode Question Link

https://leetcode.com/problems/longest-valid-parentheses

Thinking Process

The most straightfowrad solution is to find out all the substrings, and then check each of them to see if they are well-formed parenthesis. If N is the size of the string, the time complexity is O(N^3).

Given that the scale of the question is 3 * 10^4, it is unlikely that we can pass if we are not O(N). So let’s see if we can do it within O(N) or O(N * lg N).

Let’s assume that F(i) means the longest well-formed parenthesis ending at position i.

First of all, F(0) = 0.

For any position after 0, we can break down the string into this:

s = ... x x x x x x x x x x x x x s[i] . . .

For F(i), therer are two cases:

• If the orange character is ( and s[i] == ')', it means from the substring from the orange character to s[i] is a well-formed parenthesis, because we know the green part before s[i] is a well-formed parenthesis. To make it even longer, we can add up the well-formed parenthesis before the orange character, i.e., the red part. In other words, F(i) = 2 + F(i - 1) + F(i - F(i - 1) - 2).
• Otherwise, if the orange character is not ( or s[i] != ')', it means there is no well-formed parenthesis ending at position i. In this case, F(i) = 0.

The above algorithm can help us calculate each F(i) in O(1) time. So we just need to calculate all the F(i)s, and then return the maximum one.

Time & Space Complexity

Assuming N is the size of the string:

• Time complexity: O(N)
• Space complexity: O(N)

Solution

class Solution {
public:
    int longestValidParentheses(string s) {
        vector<int> dp(s.size());

        int max_len = 0;

        for (int i = 1; i < s.size(); i++)
        {
            int l = i - 1 - dp[i - 1];

            if (s[i] == ')' && s[l] == '(')
            {
                dp[i] = dp[i - 1] + 2;
                if (l > 0)
                    dp[i] += dp[l - 1];
            }

            max_len = max(max_len, dp[i]);
        }

        return max_len;
    }
};