这道题的解决方案基于图的深度优先搜索。首先,记录每个字符在字符串中的所有位置,然后构建一个图,图中的每个节点代表一个字符,边表示两个字符的位置有重叠,即一个字符的位置区间包含了另一个字符。对每个字符执行深度优先搜索,以确定可以合并为一个最小区间的所有字符,这个区间就代表了一个有效的子字符串。所有这些子字符串根据长度进行排序,最后通过遍历这些区间,选择那些不重叠的区间,即构成解的一部分。算法需要确保每个字符至多只在一个选择的子字符串中出现。
时间复杂度: O(n + 26^2 + V log V)
空间复杂度: O(n + V)
# Enhanced with comments for clarity
class Solution:
def maxNumOfSubstrings(self, s: str) -> List[str]:
# Track positions of each character
positions = defaultdict(list)
for i, c in enumerate(s):
positions[c].append(i)
# Build a graph to find overlaps
graph = defaultdict(list)
# Create edges between characters that overlap
for c1 in positions:
for c2 in positions:
if c1 != c2:
c1_left, c1_right = positions[c1][0], positions[c1][-1]
c2_position = positions[c2]
if bisect_right(c2_position, c1_right) != bisect_right(c2_position, c1_left):
graph[c1].append(c2)
subs = []
# Find minimal covering substring using DFS
def dfs(c, visited: set) -> (int, int):
l, r = positions[c][0], positions[c][-1]
visited.add(c)
for nxt in graph[c]:
if nxt not in visited:
nl, nr = dfs(nxt, visited)
l, r = min(l, nl), max(r, nr)
return l, r
# Search for all substrings
for c in positions:
visited = set()
c2_position, r = dfs(c, visited)
subs.append(((c2_position, r), visited))
# Sort by length
subs.sort(key=lambda p: p[0][1] - p[0][0])
left = set(positions.keys())
ans = []
# Select non-overlapping substrings
for (c2_position, r), visited in subs:
if not visited - left:
ans.append(s[c2_position:r + 1])
left -= visited
return ans