{"id":7122,"date":"2020-07-19T00:12:08","date_gmt":"2020-07-19T07:12:08","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7122"},"modified":"2020-07-19T22:07:02","modified_gmt":"2020-07-20T05:07:02","slug":"leetcode-1520-maximum-number-of-non-overlapping-substrings","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-1520-maximum-number-of-non-overlapping-substrings\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1520. Maximum Number of Non-Overlapping Substrings"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1520. Maximum Number of Non-Overlapping Substrings - \u5237\u9898\u627e\u5de5\u4f5c EP344\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/yAeI2uo3GP8?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>Given a string&nbsp;<code>s<\/code>&nbsp;of lowercase letters, you need to find the maximum number of&nbsp;<strong>non-empty<\/strong>&nbsp;substrings of&nbsp;<code>s<\/code>&nbsp;that meet the following conditions:<\/p>\n\n\n\n<ol class=\"wp-block-list\"><li>The substrings do not overlap, that is for any two substrings&nbsp;<code>s[i..j]<\/code>&nbsp;and&nbsp;<code>s[k..l]<\/code>, either&nbsp;<code>j &lt; k<\/code>&nbsp;or&nbsp;<code>i &gt; l<\/code>&nbsp;is true.<\/li><li>A substring that contains a certain character&nbsp;<code>c<\/code>&nbsp;must also contain all occurrences of&nbsp;<code>c<\/code>.<\/li><\/ol>\n\n\n\n<p>Find&nbsp;<em>the maximum number of substrings that meet the above conditions<\/em>. If there are multiple solutions with the same number of substrings,&nbsp;<em>return the one with minimum total length.&nbsp;<\/em>It can be shown that there exists a unique solution of minimum total length.<\/p>\n\n\n\n<p>Notice that you can return the substrings in&nbsp;<strong>any<\/strong>&nbsp;order.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> s = \"adefaddaccc\"\n<strong>Output:<\/strong> [\"e\",\"f\",\"ccc\"]\n<strong>Explanation:<\/strong>&nbsp;The following are all the possible substrings that meet the conditions:\n[\n&nbsp; \"adefaddaccc\"\n&nbsp; \"adefadda\",\n&nbsp; \"ef\",\n&nbsp; \"e\",\n  \"f\",\n&nbsp; \"ccc\",\n]\nIf we choose the first string, we cannot choose anything else and we'd get only 1. If we choose \"adefadda\", we are left with \"ccc\" which is the only one that doesn't overlap, thus obtaining 2 substrings. Notice also, that it's not optimal to choose \"ef\" since it can be split into two. Therefore, the optimal way is to choose [\"e\",\"f\",\"ccc\"] which gives us 3 substrings. No other solution of the same number of substrings exist.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> s = \"abbaccd\"\n<strong>Output:<\/strong> [\"d\",\"bb\",\"cc\"]\n<strong>Explanation: <\/strong>Notice that while the set of substrings [\"d\",\"abba\",\"cc\"] also has length 3, it's considered incorrect since it has larger total length.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= s.length &lt;= 10^5<\/code><\/li><li><code>s<\/code>&nbsp;contains only lowercase English letters.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Greedy<\/strong><\/h2>\n\n\n\n<p>Observation: If a valid substring contains shorter valid strings, ignore the longer one and use the shorter one.<br>e.g. &#8220;abbeefba&#8221; is a valid substring, however, it includes &#8220;bbeefb&#8221;, &#8220;ee&#8221;, &#8220;f&#8221; three valid substrings, thus it won&#8217;t be part of the optimal solution, since we can always choose a shorter one, with potential to have one or more non-overlapping substrings. For &#8220;bbeefb&#8221;, again it includes &#8220;ee&#8221; and &#8220;f&#8221;, so it won&#8217;t be optimal either. Thus, the optimal ones are &#8220;ee&#8221; and &#8220;f&#8221;.<\/p>\n\n\n\n<ol class=\"wp-block-list\"><li>We just need to record the first and last occurrence of each character<\/li><li>When we meet a character for the first time we must include everything from current pos to it&#8217;s last position. e.g. &#8220;<strong>a<\/strong>bbeefb<strong>a<\/strong>&#8221; | ccc, from first &#8216;a&#8217; to last &#8216;a&#8217;, we need to cover &#8220;abbeefba&#8221;<\/li><li>If any character in that range has larger end position, we must extend the string. e.g. &#8220;<strong>a<\/strong>bc<strong>a<\/strong>bbcc&#8221; | efg, from first &#8216;a&#8217; to last &#8216;a&#8217;, we have characters &#8216;b&#8217; and &#8216;c&#8217;, so we have to extend the string to cover all &#8216;b&#8217;s and &#8216;c&#8217;s. Our first valid substring extended from &#8220;abca&#8221; to &#8220;abcabbcc&#8221;.<\/li><li>If any character in the covered range has a smallest first occurrence, then it&#8217;s an invalid substring. e.g. ab | &#8220;cbc&#8221;, from first &#8216;c&#8217; to last &#8216;c&#8217;, we have &#8216;b&#8217;, but &#8216;b&#8217; is not fully covered, thus &#8220;cbc&#8221; is an invalid substring.<\/li><li>For the first valid substring, we append it to the ans array. &#8220;abbeefba&#8221; =&gt; ans = [&#8220;abbeefba&#8221;]<\/li><li>If we find a shorter substring that is full covered by the previous valid substring, we replace that substring with the shorter one. e.g.<br>&#8220;abbeefba&#8221; | ccc =&gt; ans = [&#8220;abbeefba&#8221;]<br>&#8220;<span style=\"text-decoration: underline;\">a<strong>bbeefb<\/strong>a<\/span>&#8221; | ccc =&gt; ans = [&#8220;bbeefb&#8221;]<br>&#8220;a<span style=\"text-decoration: underline;\">bb<strong>ee<\/strong>fb<\/span>a&#8221; | ccc =&gt; ans = [&#8220;ee&#8221;]<\/li><li>If the current substring does not overlap with previous one, append it to ans array.<br>&#8220;abb<strong>ee<\/strong>fba&#8221; | ccc =&gt; ans = [&#8220;ee&#8221;]<br>&#8220;abbee<strong>f<\/strong>ba&#8221; | ccc =&gt; ans = [&#8220;ee&#8221;, &#8220;f&#8221;]<br>&#8220;abbeefba<strong>ccc<\/strong>&#8221; =&gt; ans = [&#8220;ee&#8221;, &#8220;f&#8221;, &#8220;ccc&#8221;]<\/li><\/ol>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector<string> maxNumOfSubstrings(const string& s) {\n    const int n = s.length();    \n    vector<int> l(26, INT_MAX);\n    vector<int> r(26, INT_MIN);\n    for (int i = 0; i < n; ++i) {\n      l[s[i] - 'a'] = min(l[s[i] - 'a'], i);\n      r[s[i] - 'a'] = max(r[s[i] - 'a'], i);\n    }\n    auto extend = [&#038;](int i) -> int {      \n      int p = r[s[i] - 'a'];\n      for (int j = i; j <= p; ++j) {\n        if (l[s[j] - 'a'] < i) \/\/ invalid substring\n          return -1; \/\/ e.g. a|\"ba\"...b\n        p = max(p, r[s[j] - 'a']);\n      }\n      return p;\n    };\n    \n    vector<string> ans;\n    int last = -1;\n    for (int i = 0; i < n; ++i) {\n      if (i != l[s[i] - 'a']) continue;\n      int p = extend(i);\n      if (p == -1) continue;\n      if (i > last) ans.push_back(\"\");\n      ans.back() = s.substr(i, p - i + 1);\n      last = p;      \n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Given a string&nbsp;s&nbsp;of lowercase letters, you need to find the maximum number of&nbsp;non-empty&nbsp;substrings of&nbsp;s&nbsp;that meet the following conditions: The substrings do not overlap, that is&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[51],"tags":[88,177,635,4,41,314],"class_list":["post-7122","post","type-post","status-publish","format-standard","hentry","category-greedy","tag-greedy","tag-medium","tag-non-overlapping","tag-string","tag-subarray","tag-substring","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7122","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=7122"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7122\/revisions"}],"predecessor-version":[{"id":7129,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7122\/revisions\/7129"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7122"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7122"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7122"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}