5466. 最多的不重叠子字符串 [medium]
5466. 最多的不重叠子字符串 [medium]
周赛198
通过的用户数161
尝试过的用户数675
用户总通过次数165
用户总提交次数1640
题目难度Medium
给你一个只包含小写字母的字符串 s ，你需要找到 s 中最多数目的非空子字符串，满足如下条件：
这些字符串之间互不重叠，也就是说对于任意两个子字符串 s[i..j] 和 s[k..l] ，要么 j < k 要么 i > l 。 如果一个子字符串包含字符 c ，那么 s 中所有 c 字符都应该在这个子字符串中。 请你找到满足上述条件的最多子字符串数目。如果有多个解法有相同的子字符串数目，请返回这些子字符串总长度最小的一个解。可以证明最小总长度解是唯一的。
请注意，你可以以 任意 顺序返回最优解的子字符串。
示例 1：
输入：s = "adefaddaccc"
输出：["e","f","ccc"]
解释：下面为所有满足第二个条件的子字符串：
[
"adefaddaccc"
"adefadda",
"ef",
"e",
"f",
"ccc",
]
如果我们选择第一个字符串，那么我们无法再选择其他任何字符串，所以答案为 1 。如果我们选择 "adefadda" ，剩下子字符串中我们只可以选择 "ccc" ，它是唯一不重叠的子字符串，所以答案为 2 。同时我们可以发现，选择 "ef" 不是最优的，因为它可以被拆分成 2 个子字符串。所以最优解是选择 ["e","f","ccc"] ，答案为 3 。不存在别的相同数目子字符串解。
示例 2：
输入：s = "abbaccd"
输出：["d","bb","cc"]
解释：注意到解 ["d","abba","cc"] 答案也为 3 ，但它不是最优解，因为它的总长度更长。
提示：
- 1 <= s.length <= 10^5
- s 只包含小写英文字母。
Second Try
2020-07-21
被这道题折腾了许久，周赛结束后看其他个人解法，思路不同写法不同有时候真是很难理解，有些作者说其实自己也理解不透彻只是刚好写出来通过了。
终于等到官方题解，然后一眼就看清楚了。 在某个坐标轴上按不相交原则放置最多的集合，需要的只是一个贪心算法。
集合的筛选本身在first try里我就写出来了，不过看起来还是下面的解法更巧妙一些：每次一更新range范围，就更新起点，从最左边从头遍历一次。虽然有许多重复的冗余，但也保证了范围内都是符合条件的字符：在s内的c都在该子字符串内。
然后不重复排更多区间原来很简单，就是按right右边界进行排序就行了，这样能保证右边能放更多可能的元素。如果右边界相同，那么选取长度最短的（也就是left最大的），这样能保证左边能放更多区间。
具体到这道题，按照第二步扩展出来的区间其实并不存在相同right边界的区间，最多是出现一些重复的区间，或者是嵌套的区间。因此排序的时候只需要按照right排序即可，然后遍历的时候注意下一个待选区间没有包括上一个区间即可（也就是下一个的left必定要在上一个的right后面）。
然后自然而然结果就出来了。没有想明白这贪心算法，浪费了周赛的一个小时，赛后的几个小时，套路见得还太少，哎。
- 官方题解
- 这是排序加入了长度的版本
class Solution(object):
def maxNumOfSubstrings(self, s):
"""
:type s: str
:rtype: List[str]
"""
# czone: char: [left, right]
czone = collections.defaultdict(list)
for idx, c in enumerate(s):
if len(czone[c]) == 0:
czone[c] = [idx, idx]
else:
czone[c][1] = idx
# print('czone', czone)
# gaps: [lft, rt]
gaps = []
for arr in czone.values():
lft, rt = arr
i = lft
while i <= rt:
if czone[s[i]][0] >= lft and czone[s[i]][1] <= rt:
i += 1
continue
lft = min(lft, czone[s[i]][0])
rt = max(rt, czone[s[i]][1])
i = lft
gaps.append([lft, rt, rt - lft + 1])
# 按照右边界排序，如果右边界相同，则考虑最短长度，以便在左边放入更多元素
gaps = sorted(gaps, key=lambda arr: [arr[1], arr[2]])
# print("gaps", gaps)
seq = []
for arr in gaps:
if len(seq):
if seq[-1][1] >= arr[0]:
continue
seq.append(arr)
# print('seq', seq)
rv = []
for arr in seq:
rv.append(s[arr[0]: arr[1] + 1])
return rv
- improved version
排序并不需要考虑长度，仅仅考虑右边界的版本
class Solution(object):
def maxNumOfSubstrings(self, s):
"""
:type s: str
:rtype: List[str]
"""
# czone: char: [left, right]
czone = collections.defaultdict(list)
for idx, c in enumerate(s):
if len(czone[c]) == 0:
czone[c] = [idx, idx]
else:
czone[c][1] = idx
# gaps: [lft, rt]
gaps = []
for arr in czone.values():
lft, rt = arr
i = lft
while i <= rt:
if czone[s[i]][0] >= lft and czone[s[i]][1] <= rt:
i += 1
continue
lft = min(lft, czone[s[i]][0])
rt = max(rt, czone[s[i]][1])
i = lft
gaps.append([lft, rt])
# 按照右边界排序
gaps = sorted(gaps, key=lambda arr: arr[1])
seq = []
for arr in gaps:
if len(seq):
# 如果已经在上一个的范围内，则跳过
if seq[-1][1] >= arr[0]:
continue
seq.append(arr)
rv = []
for arr in seq:
rv.append(s[arr[0]: arr[1] + 1])
return rv
- 执行用时：1624 ms, 在所有 Python 提交中击败了100.00%的用户
- 内存消耗：14.6 MB, 在所有 Python 提交中击败了100.00%的用户
First Try
failed try
2020-07-19
一开始理解题目花了很长时间，终于明白这个应该是在多个集合中寻找最多的非相交集合。 各种测试，考虑额外的条件，比如a的字符串中，如果包含其他字符串b，则要确保整个字符串s中的所有b都在这个a的子字符串内，于是再次扩展a的范围，把b都放进来，然后递归再考虑放进来后b的范围。
好不容易写完了，解决了各种bug，也通过了前面的几个测试案例，结果超时了。 超时是很容易看到的，毕竟在选择后序的时候，从某个点开始会被不断重复。 但是没想到该怎么写一个动态dp的缓存版本，因为这里面要求返回的不是长度，而是所有子字符串啊。
最后还是放弃了，浪费了一个多小时的时间。 周赛也挂在这道题上了。
class Solution:
def maxNumOfSubstrings(self, s: str) -> List[str]:
marks = collections.defaultdict(list)
for idx, c in enumerate(s):
if len(marks[c]) <= 1:
marks[c].append(idx)
else:
marks[c][1] = idx
for k, v in marks.items():
if len(marks[k]) == 1:
marks[k].append(v[0])
# marks[k].append([v[1] - v[0] + 1])
# print('prev marks', marks)
# 在子字符串内的字符c，必须包含整体字符s里的所有c, 因此必须设置真正的范围
for k in marks:
start, end = marks[k]
while True:
m_start, m_end = start, end
for i in range(start, end + 1):
start = min(marks[s[i]][0], start)
end = max(marks[s[i]][1], end)
if m_start == start and m_end == end:
marks[k] = [start, end]
break
# print("start", start, , "end", end, new_end)
print("new marks", marks)
spoints = dict()
for k, v in marks.items():
spoints[v[0]] = [v[1], k]
starts = sorted(spoints.keys())
# print('spoints', spoints)
# print("starts", starts)
rv = []
cache = dict()
def select(start, seq, rv):
available_starts = [s for s in starts if s >= start]
# print("start", start, "available starts", available_starts)
if not len(available_starts):
rv.append(seq[:])
# print("one part finish", rv)
return
for select_start in available_starts:
end, c = spoints[select_start]
# for i in range(select_start, end + 1):
# end = max(end, marks[s[i]][1])
seq.append(s[select_start:end+1])
select(end + 1, seq, rv)
seq.pop()
select(0, [], rv)
# print("rv", rv)
cols = []
maxlen = max([len(seq) for seq in rv])
for seq in rv:
if len(seq) == maxlen:
cols.append(seq)
# print("last", cols)
rrv = cols[0]
for seq in cols:
if len(''.join(seq)) < len(''.join(rrv)):
rrv = seq
return rrv
# 输入：
# "abab"
# 输出：
# ["aba"]
# 预期：
# ["abab"]