{"id":7180,"date":"2020-07-29T12:12:56","date_gmt":"2020-07-29T19:12:56","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7180"},"modified":"2020-07-29T12:19:53","modified_gmt":"2020-07-29T19:19:53","slug":"leetcode-1513-number-of-substrings-with-only-1s","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1513-number-of-substrings-with-only-1s\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1513. Number of Substrings With Only 1s"},"content":{"rendered":"\n

Given a binary string s<\/code> (a string consisting only of ‘0’ and ‘1’s).<\/p>\n\n\n\n

Return the number of substrings with all characters 1’s.<\/p>\n\n\n\n

Since the answer may be too large, return it modulo 10^9 + 7.<\/p>\n\n\n\n

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

Input:<\/strong> s = \"0110111\"\nOutput:<\/strong> 9\nExplanation: <\/strong>There are 9 substring in total with only 1's characters.\n\"1\" -> 5 times.\n\"11\" -> 3 times.\n\"111\" -> 1 time.<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> s = \"101\"\nOutput:<\/strong> 2\nExplanation: <\/strong>Substring \"1\" is shown 2 times in s.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> s = \"111111\"\nOutput:<\/strong> 21\nExplanation: <\/strong>Each substring contains only 1's characters.\n<\/pre>\n\n\n\n
Example 4:<\/strong><\/p>\n\n\n\n
Input:<\/strong> s = \"000\"\nOutput:<\/strong> 0\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • s[i] == '0'<\/code> or s[i] == '1'<\/code><\/li>
  • 1 <= s.length <= 10^5<\/code><\/li><\/ul>\n\n\n\n
    Solution: DP<\/strong> \/ Prefix Sum<\/strong><\/h2>\n\n\n\n
    dp[i] := # of all 1 subarrays end with s[i].
    dp[i] = dp[i-1] if s[i] == \u20181\u2018 else 0
    ans = sum(dp)
    s=1101
    dp[0] = 1 \/\/ 1
    dp[1] = 2 \/\/ 11, *1
    dp[2] = 0 \/\/ None
    dp[3] = 1 \/\/ ***1
    ans = 1 + 2 + 1 = 5<\/p>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \nclass Solution {\npublic:\n  int numSub(string s) {\n    constexpr int kMod = 1e9 + 7;\n    long ans = 0;\n    vector dp(s.length() + 1);\n    for (int i = 1; i <= s.length(); ++i) {\n      dp[i] = s[i - 1] == '1' ? dp[i - 1] + 1 : 0;\n      ans += dp[i];\n    }\n    return ans % kMod;\n  }\n};\n<\/pre> \n<\/div><\/div>\n\n\n\n
    dp[i] only depends on dp[i-1], we can reduce the space complexity to O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    class Solution {\npublic:\n  int numSub(string s) {\n    constexpr int kMod = 1e9 + 7;\n    long ans = 0;\n    int cur = 0;\n    for (char c : s) {\n      cur = c == '1' ? cur + 1 : 0;\n      ans += cur;\n    }\n    return ans % kMod;\n  }\n};\n<\/pre> \n\n<\/div>
    Java<\/h2>\n
    \n\n
    \nclass Solution {\n  public int numSub(String s) {\n    final int kMod = 1_000_000_000 + 7;\n    int ans = 0;\n    int cur = 0;\n    for (int i = 0; i < s.length(); ++i) {\n      cur = s.charAt(i) == '1' ? cur + 1 : 0;\n      ans = (ans + cur) % kMod;\n    }\n    return ans;\n  }\n}\n<\/pre>\n\n<\/div>
    Python3<\/h2>\n
    \n\n
    \nclass Solution:\n  def numSub(self, s: str) -> int:\n    kMod = 10**9 + 7\n    ans = 0\n    cur = 0\n    for c in s:\n      cur = cur + 1 if c == '1' else 0\n      ans += cur\n    return ans % kMod\n<\/pre>\n<\/div><\/div>\n\n\n\n

    <\/p>\n","protected":false},"excerpt":{"rendered":"
    Given a binary string s (a string consisting only of ‘0’ and ‘1’s). Return the number of substrings with all characters 1’s. Since the answer may be too…<\/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,177,200,41],"class_list":["post-7180","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-medium","tag-prefix-sum","tag-subarray","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7180","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=7180"}],"version-history":[{"count":6,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7180\/revisions"}],"predecessor-version":[{"id":7187,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7180\/revisions\/7187"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7180"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7180"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7180"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}