Maximum Number of Non-Overlapping Substrings
Given a string s of lowercase letters, find the maximum number of non-empty substrings of s that meet the following conditions:
- The substrings do not overlap; that is, for any two substrings
s[i..j]ands[x..y], eitherj < xori > yis true. - A substring that contains a certain character
cmust also contain all occurrences ofc.
Return the maximum number of substrings that meet the above conditions. If there are multiple solutions with the same number of substrings, return the one with minimum total length. It can be shown that there exists a unique solution of minimum total length.
Notice that you can return the substrings in any order.
Example 1
Input
s = "adefaddaccc"Output
["e","f","ccc"]The optimal choice is
["e", "f", "ccc"], which gives 3 valid non-overlapping substrings; choosing larger valid substrings results in fewer substrings or a larger total length.Example 2
Input
s = "abbaccd"Output
["d","bb","cc"]The set
["d", "abba", "cc"] also has 3 substrings, but it is incorrect because it has a larger total length.Constraints
- 1 <= s.length <= 10^5
- s contains only lowercase English letters.