{"id":27,"date":"2018-06-08T00:00:51","date_gmt":"2018-06-08T00:00:51","guid":{"rendered":"https:\/\/sinyalee.com\/essays\/?p=27"},"modified":"2024-09-02T03:24:28","modified_gmt":"2024-09-02T03:24:28","slug":"leetcode-hard-32-longest-valid-parentheses","status":"publish","type":"post","link":"https:\/\/sinyalee.com\/essays\/?p=27","title":{"rendered":"[LeetCode HARD] 32 Longest Valid Parentheses"},"content":{"rendered":"

LeetCode has become the de facto go-to website for tech interviews. As a former competitive programmer, the LeetCode \u201chard\u201d, \u201cmedium\u201d, and \u201ceasy\u201d problems are more like \u201ceasy\u201d, \u201cvery easy\u201d, \u201cextremely easy\u201d 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.<\/p>\n

This is my 4th LeetCode solution article, for\u00a0LeetCode Problem 32, Longest Valid Parentheses<\/a>.<\/p>\n

Problem<\/h3>\n

Given a string of left and right parenthesis symbols, find the length of longest valid substring which is a valid parentheses string.<\/p>\n

Solution<\/h3>\n

Let\u00a0f(i)<\/em>\u00a0be 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\u00a0f(i)<\/em>.<\/p>\n

Now we can try to find out how to compute\u00a0f(i)<\/em>.<\/p>\n

If the i-th character is \u2018)\u2019, any substrings starting from the i-th character must be invalid. Thus\u00a0f(i) = 0<\/em>.<\/p>\n

Now we consider the case that the i-th character is \u2018(\u2019. 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 \u2018)\u2019, we know that we can never find a closing parentheses and thus f(i) = 0.<\/p>\n

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<\/p>\n

f(i) = f(i+1) + 2 + f(i + f(i+1) + 2)<\/em><\/p>\n

Source Code<\/h3>\n
\nint longestValidParentheses(string s) {\n    int ret = 0;\n    std::vector f(s.size()+1, 0);\n    for (int i = s.size() - 1; i >= 0; --i)\n        if (s[i] == '(' && i+1 + f[i+1] < s.size() && s[i+1 + f[i+1]] == ')') {\n            f[i] = f[i+1] + 2 + f[i+1 + f[i+1] + 1];\n            ret = std::max(f[i], ret);\n        }\n    return ret;\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
LeetCode has become the de facto go-to website for tech interviews. As a former competitive programmer, the LeetCode \u201chard\u201d, \u201cmedium\u201d, and \u201ceasy\u201d problems are more like \u201ceasy\u201d, \u201cvery easy\u201d, \u201cextremely easy\u201d for me. I think it would be a good idea for me to put my solutions of some of the LeetCode hard problems here. […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8],"tags":[],"class_list":["post-27","post","type-post","status-publish","format-standard","hentry","category-coding"],"_links":{"self":[{"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=\/wp\/v2\/posts\/27","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=27"}],"version-history":[{"count":28,"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=\/wp\/v2\/posts\/27\/revisions"}],"predecessor-version":[{"id":130,"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=\/wp\/v2\/posts\/27\/revisions\/130"}],"wp:attachment":[{"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=27"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=27"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=27"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}