#1520
Maximum Number of Non-Overlapping Substrings
master · 1665 · lc hard +32 · verified · 41.6% accepted · 885 likes · top 22%
Description
Given a lowercase string s, select the maximum number of non-overlapping, non-empty substrings such that each selected substring contains every occurrence of every character it includes. Among all selections achieving the maximum count, return the one with minimum total length (guaranteed unique). The substrings may be returned in any order.
Example 1:
Input: s = "adefaddaccc"
Output: ["e","f","ccc"]
Explanation: The following are all the possible substrings that meet the conditions:
[
"adefaddaccc"
"adefadda",
"ef",
"e",
"f",
"ccc",
]
If 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.
Example 2:
Input: s = "abbaccd"
Output: ["d","bb","cc"]
Explanation: Notice that while the set of substrings ["d","abba","cc"] also has length 3, it's considered incorrect since it has larger total length.
Code
1
2
3