[LeetCode HARD] 32 Longest Valid Parentheses

LeetCode has become the de facto go-to website for tech interviews. As a former competitive programmer, the LeetCode “hard”, “medium”, and “easy” problems are more like “easy”, “very easy”, “extremely easy” for me. I think it would be a good idea for me to put my solutions of some of the LeetCode hard problems here. Hope it would be helpful for people who are preparing for tech interviews.

This is my 4th LeetCode solution article, for LeetCode Problem 32, Longest Valid Parentheses.

Problem

Given a string of left and right parenthesis symbols, find the length of longest valid substring which is a valid parentheses string.

Solution

Let f(i) be the length of the length of the longest valid substring starting from the i-th character. Then the final solution if the largest of all possible f(i).

Now we can try to find out how to compute f(i).

If the i-th character is ‘)’, any substrings starting from the i-th character must be invalid. Thus f(i) = 0.

Now we consider the case that the i-th character is ‘(’. First we need to find its corresponding closing parenthesis. If a valid closing parenthesis exists, the substring between them must be a valid parentheses string. Moreover, it must be the longest possible valid parentheses string starting from (i+1)-th character. Thus we know that the closing parentheses must be the (i+1 + f(i+1))-th character. If this character is not ‘)’, we know that we can never find a closing parentheses and thus f(i) = 0.

Now we consider the final case: the (i+1 + f(i+1))-th character is indeed a closing parenthesis. To find the longest possible valid substring, we need to keep going and see if we can concatenate more valid parentheses substring if possible. The longest we can go is f(i+1 + f(i+1) + 1). Therefore we have

f(i) = f(i+1) + 2 + f(i + f(i+1) + 2)

Source Code

int longestValidParentheses(string s) {
    int ret = 0;
    std::vector f(s.size()+1, 0);
    for (int i = s.size() - 1; i >= 0; --i)
        if (s[i] == '(' && i+1 + f[i+1] < s.size() && s[i+1 + f[i+1]] == ')') {
            f[i] = f[i+1] + 2 + f[i+1 + f[i+1] + 1];
            ret = std::max(f[i], ret);
        }
    return ret;
}