Given a strings
of lowercase letters, you need to find the maximum number of non-emptysubstrings ofs
that meet the following conditions: The substrings do not overlap, that is for any two substringss[i..j]
ands[k..l]
, eitherj < k
ori > l
is true. A substring that contains a certain characterc
must also contain all occurrences ofc
. Find 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"] Example 2: Input: s = "abbaccd" Output: ["d","bb","cc"]
This is actually very similar to Find maximum meetings in one room – we can find the boundaries for all substrings and when we try to find the as many as possible substrings, it’s exactly the same as finding the largest number of meetings (substrings) for one room (the substrings do not overlap).
The following solution is from inspired by @bobby569.
class Solution:
def maxNumOfSubstrings(self, s: str) -> List[str]:
dic = {c: [s.index(c), s.rindex(c)+1] for c in set(s)}
substr = []
for c in set(s):
l = dic[c][0]
r = dic[c][1]
l0,r0 = float('inf'),float('-inf')
while True:
t = set(s[l:r])
for k in t:
l0 = min(l0, dic[k][0])
r0 = max(r0, dic[k][1])
if l==l0 and r==r0:
break
l, r = l0, r0
substr.append([l, r])
# Find maximum meetings in one room
substr.sort(key=lambda x: x[1])
res, last = [], 0
for b, e in substr:
if b >= last:
res.append(s[b:e])
last = e
return res