Longest Valid Parentheses, Hard Problem in O(n^2)
Problem is here: https://leetcode.com/problems/longest-valid-parentheses/description/
Given a string containing just the characters
'(' and ')', find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"
Example 2:
Input: "My solution isn't the best, but it passes with an N^2-time complexity: two tested loops, looking for the best solution starting at the outer-loop index, optimizing whenever we end up at an invalid substring. If you look at the official solution, you'll find very lean and elegant DP solutions for this problem. Sometimes if you can't find the best solution, at least find a better solution than the worst-case (in our case, N^3). Cheers, ACC.)()())" Output: 4 Explanation: The longest valid parentheses substring is"()()"
public class Solution
{
public int LongestValidParentheses(string s)
{
if (String.IsNullOrEmpty(s)) return 0;
int max = 0;
for (int i = 0; i < s.Length; i++)
{
if (s[i] == '(')
{
int open = 1;
for (int j = i + 1; j < s.Length; j++)
{
if (s[j] == ')') open--;
else if (s[j] == '(') open++;
if (open < 0) break;
if (open == 0) max = Math.Max(max, j - i + 1);
}
}
}
return max;
}
}
Sleek! My solution is has a O(N) space complexity but uses O(N) of extra memory:
ReplyDeleteclass Solution {
public:
int longestValidParentheses(string s) {
if (s.size() < 2) return 0;
int d[s.size()];
d[s.size()-1] = 0;
d[s.size()-2] = (s[s.size()-2] == '(' && s.back() == ')') ? 2 : 0;
int longest_so_far = d[s.size()-2];
for (int i = s.size()-3; i >= 0; --i) {
d[i] = 0;
if (s[i] != '(') continue; // only ( can start a valid string
int closing_expected_at = i + d[i+1] + 1;
if (closing_expected_at < s.size() && s[closing_expected_at] == ')') {
d[i] = d[i+1] + 2;
if (closing_expected_at+1 < s.size()) {
d[i] += d[closing_expected_at + 1];
}
longest_so_far = max(longest_so_far, d[i]);
}
}
return longest_so_far;
}
};
https://gist.github.com/ttsugriy/3ad7c1c7033d820ea5c6e860a20099b5
The solution is based on the following observation - if we use d[i] to store the length of the valid string starting at i, while scanning backwards for each index that points at the opening parenthesis we can check if the character that follows the longest valid string at its right (i + d[i+1] + 1) is a closing parenthesis and if so, the entire string i + d[i] is valid, which may additionally be followed by another valid sequence that starts after the closing parenthesis.