1520. Maximum Number of Non-Overlapping Substrings ================================================== 题目信息 -------- :题号: 1520 :难度: Hard :主题: 字符串、贪心、区间 :原题: `LeetCode 1520 `_ :重点: 每个选中子串若包含某字符,就必须包含该字符在原串中的全部出现位置;先最大化子串数量,再最小化总长度 题目重述 -------- 给定小写字符串 ``s``。需要选择若干互不重叠的非空连续子串。对于任意选中子串,只要其中出现字符 ``c``,该字符在整个 ``s`` 中的所有出现位置都必须落在这个子串内。 首先最大化选中子串数量;若存在多种数量相同的方案,再使所有子串总长度最小。请返回任意满足要求的子串列表。 ``1 <= s.length <= 10^5``,``s`` 只包含小写英文字母。 自建示例 -------- 应选择更短的合法区间以减小总长度: .. code-block:: text 输入:s = "abbaccd" 输出:["bb","cc","d"] 解释:三个子串互不重叠,并分别包含其中字符的全部出现位置;数量为三且总长度最小。 所有字符相同时只能选择整个字符串: .. code-block:: text 输入:s = "aaaa" 输出:["aaaa"] 解释:任何包含 a 的合法子串都必须覆盖全部四个 a。