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: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"
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.


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;
 }
}

Comments

  1. TarasFebruary 7, 2019 at 6:57 PM

    Sleek! My solution is has a O(N) space complexity but uses O(N) of extra memory:


    class 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.

    ReplyDelete

Post a Comment

Popular posts from this blog

Count Binary Substrings

-
Image
Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
Read more

Count Vowels Permutation: Standard DP

-
Image
Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
Read more

Maximum Number of Balloons

-
Image
#431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
Read more