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