{"id":6360,"date":"2020-02-22T23:41:07","date_gmt":"2020-02-23T07:41:07","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6360"},"modified":"2020-02-22T23:46:25","modified_gmt":"2020-02-23T07:46:25","slug":"1358-number-of-substrings-containing-all-three-characters","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/string\/1358-number-of-substrings-containing-all-three-characters\/","title":{"rendered":"\u82b1\u82b1\u9171 1358. Number of Substrings Containing All Three Characters"},"content":{"rendered":"\n

Given a string s<\/code> consisting only of characters a<\/em>, b<\/em> and c<\/em>.<\/p>\n\n\n\n

Return the number of substrings containing at least<\/strong> one occurrence of all these characters a<\/em>, b<\/em> and c<\/em>.<\/p>\n\n\n\n

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

Input:<\/strong> s = \"abcabc\"\nOutput:<\/strong> 10\nExplanation:<\/strong> The substrings containing at least one occurrence of the characters a<\/em>, b<\/em> and c are \"<\/em>abc\", \"<\/em>abca\", \"<\/em>abcab\", \"<\/em>abcabc\", \"<\/em>bca\", \"<\/em>bcab\", \"<\/em>bcabc\", \"<\/em>cab\", \"<\/em>cabc\" <\/em>and \"<\/em>abc\" <\/em>(again<\/strong>). <\/em>\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> s = \"aaacb\"\nOutput:<\/strong> 3\nExplanation:<\/strong> The substrings containing at least one occurrence of the characters a<\/em>, b<\/em> and c are \"<\/em>aaacb\", \"<\/em>aacb\" <\/em>and \"<\/em>acb\".<\/em>\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> s = \"abc\"\nOutput:<\/strong> 1\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 3 <= s.length <= 5 x 10^4<\/code><\/li>
  • s<\/code> only consists of a<\/em>, b<\/em> or c <\/em>characters.<\/li><\/ul>\n\n\n\n
    Solution<\/strong><\/h2>\n\n\n\n
    Record the last index of each character. <\/p>\n\n\n\n
    At each index i, we can choose any index j that j <= min(last_a, last_b, last_c) as the starting point, and there will be  min(last_a, last_b, last_c) + 1 valid substrings.<\/p>\n\n\n\n
    e.g. aabbabcc…
    last_a = 4
    last_b = 5
    last_c = 7
    min(last_a, last_b, last_c) = 4
    aabba | bcc
    We can choose any char with index <= 4 as string point, there are 5 of them:
    aabbabcc
    abbabcc
    bbabcc
    babcc
    abcc<\/p>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int numberOfSubstrings(string s) {\n    vector l{-1,-1,-1};\n    int ans = 0;\n    for (size_t i = 0; i < s.length(); ++i) {\n      l[s[i] - 'a'] = i;\n      ans += 1 + *min_element(begin(l), end(l));\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
    \n
    Python3<\/h2>\n
    \n\n
    # Author: Huahua\nclass Solution:\n  def numberOfSubstrings(self, s: str) -> int:\n    l = {'a':-1, 'b':-1, 'c':-1}\n    ans = 0\n    for i, ch in enumerate(s):\n      l[ch] = i\n      ans += min(l.values()) + 1\n    return ans\n<\/pre>\n<\/div><\/div>\n\n\n\n
    <\/p>\n","protected":false},"excerpt":{"rendered":"
    Given a string s consisting only of characters a, b and c. Return the number of substrings containing at least one occurrence of all these characters a, b and c. Example 1: Input: s = “abcabc” Output:…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[47],"tags":[82,177,314],"class_list":["post-6360","post","type-post","status-publish","format-standard","hentry","category-string","tag-hashtable","tag-medium","tag-substring","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6360","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=6360"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6360\/revisions"}],"predecessor-version":[{"id":6363,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6360\/revisions\/6363"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6360"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6360"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6360"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}