{"id":4309,"date":"2018-11-14T01:04:29","date_gmt":"2018-11-14T09:04:29","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4309"},"modified":"2018-11-14T01:06:28","modified_gmt":"2018-11-14T09:06:28","slug":"leetcode-940-distinct-subsequences-ii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-940-distinct-subsequences-ii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 940. Distinct Subsequences II"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

Given a string\u00a0S<\/code>, count the number of distinct, non-empty subsequences of\u00a0S<\/code>\u00a0.<\/p>\n

Since the result may be large,\u00a0return the answer modulo\u00a010^9 + 7<\/code><\/strong>.<\/p>\n

Example 1:<\/strong><\/p>\n

Input: <\/strong>\"abc\"<\/span>\r\nOutput: <\/strong>7<\/span>\r\nExplanation<\/strong>: The 7 distinct subsequences are \"a\", \"b\", \"c\", \"ab\", \"ac\", \"bc\", and \"abc\".\r\n<\/pre>\n
Example 2:<\/strong><\/p>\n
Input: <\/strong>\"aba\"<\/span>\r\nOutput: <\/strong>6\r\n<\/span>Explanation<\/strong>: The 6 distinct subsequences are \"a\", \"b\", \"ab\", \"ba\", \"aa\" and \"aba\".\r\n<\/pre>\n
Example 3:<\/strong><\/p>\n
Input: <\/strong>\"aaa\"<\/span>\r\nOutput: <\/strong>3\r\n<\/span>Explanation<\/strong>: The 3 distinct subsequences are \"a\", \"aa\" and \"aaa\".<\/pre>\n
Note:<\/strong><\/p>\n
    \n
  1. S<\/code>\u00a0contains only lowercase letters.<\/li>\n
  2. 1 <= S.length <= 2000<\/code><\/li>\n<\/ol>\n
    Solution: DP<\/strong><\/h1>\n
    counts[i][j] := # of distinct sub sequences of s[1->i] and ends with letter j. (‘a'<= j <= ‘z’)<\/p>\n
    Initialization:<\/p>\n
    counts[*][*] = 0<\/p>\n
    Transition:<\/p>\n
    counts[i][j] = sum(counts[i-1]) + 1 if s[i] == j\u00a0 else counts[i-1][j]<\/p>\n
    ans = sum(counts[n])<\/p>\n
    e.g. S = “abc”<\/p>\n
    counts[1] = {‘a’ : 1}
    \ncounts[2] = {‘a’ : 1, ‘b’ : 1 + 1 = 2}
    \ncounts[3] = {‘a’ : 1, ‘b’ : 2, ‘c’: 1 + 2 + 1 = 4}
    \nans = sum(counts[3]) = 1 + 2 + 4 = 7<\/p>\n
    Time complexity: O(N*26)<\/p>\n
    Space complexity: O(N*26) -> O(26)<\/p>\n
    \n
    C++<\/h2>\n
    \n\n
    \/\/ Author: Huahua, running time: 12 ms\r\nclass Solution {\r\npublic:\r\n  int distinctSubseqII(string S) {\r\n    constexpr int kMod = 1e9 + 7;\r\n    std::vector<int> counts(26);\r\n    for (char c : S)\r\n      counts[c - 'a'] = accumulate(begin(counts), end(counts), 1L) % kMod;\r\n    return accumulate(begin(counts), end(counts), 0L) % kMod;\r\n  }\r\n};<\/pre>\n\n<\/div>
    Python3<\/h2>\n
    \n\n
    # Author: Huahua, running time: 64 ms\r\nclass Solution:\r\n  def distinctSubseqII(self, S):\r\n    kMod = 10**9 + 7\r\n    dp = {}\r\n    for c in S:\r\n      dp[c] = (sum(dp.values()) + 1) % kMod\r\n    return sum(dp.values()) % kMod<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Problem Given a string\u00a0S, count the number of distinct, non-empty subsequences of\u00a0S\u00a0. Since the result may be large,\u00a0return the answer modulo\u00a010^9 + 7. Example 1:…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[18,217,229],"class_list":["post-4309","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-hard","tag-subsequence","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4309","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=4309"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4309\/revisions"}],"predecessor-version":[{"id":4312,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4309\/revisions\/4312"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4309"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4309"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4309"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}