难度: Medium
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例 1：输入：s = "ababcbacadefegdehijhklij" 输出：[9,7,8] 解释： 划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。
示例 2：
输入：s = "eccbbbbdec" 输出：[10]
提示：
1 <= s.length <= 500s 仅由小写英文字母组成运行时间: 25 ms
内存: 16.1 MB
class Solution:
def partitionLabels(self, s: str) -> List[int]:
if not s:
return [0]
start = {}
end = {}
for i in range(len(s)):
if s[i] not in start.keys():
start[s[i]] = i
end[s[i]] = i
i = 0
temp_end = end[s[0]]
res = []
while i < len(s):
if i < temp_end:
if end[s[i]] > temp_end:
temp_end = end[s[i]]
i += 1
elif i == temp_end:
res.append(i-sum(res)+1)
i += 1
else:
temp_end = end[s[i]]
return res
这个题解使用了贪心算法和哈希表的思路。首先遍历字符串，用两个哈希表 start 和 end 分别记录每个字符第一次出现的下标和最后一次出现的下标。然后再次遍历字符串，用一个变量 temp_end 记录当前片段的结束下标，初始化为第一个字符最后出现的下标。遍历过程中，如果当前下标小于 temp_end，说明当前字符属于当前片段，并更新 temp_end 为当前字符最后出现的下标和 temp_end 的较大值。如果当前下标等于 temp_end，说明当前片段结束，将片段长度加入结果数组，并将 temp_end 更新为下一个字符最后出现的下标。最后返回结果数组即可。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def partitionLabels(self, s: str) -> List[int]:
if not s:
return [0]
# 记录每个字符第一次出现和最后一次出现的下标
start = {}
end = {}
for i in range(len(s)):
if s[i] not in start.keys():
start[s[i]] = i
end[s[i]] = i
i = 0
temp_end = end[s[0]]
res = []
while i < len(s):
if i < temp_end:
# 如果当前字符属于当前片段，更新片段的结束下标
if end[s[i]] > temp_end:
temp_end = end[s[i]]
i += 1
elif i == temp_end:
# 如果当前片段结束，将片段长度加入结果数组
res.append(i-sum(res)+1)
i += 1
else:
# 开启新的片段
temp_end = end[s[i]]
return res
在`start`和`end`哈希表中记录每个字符的第一次和最后一次出现的位置，主要是为了确定每个字符在字符串中的覆盖范围。这样做的目的是在后续遍历中能够确定每个片段的最大范围，即如果一个片段起始于某个字符，那么这个片段至少要扩展到该字符的最后出现位置，以确保该字符不会在其他片段中出现。这种信息帮助我们在第二次遍历时，通过不断更新片段的结束位置`temp_end`，来确定是否可以结束当前片段并开始一个新的片段。
`temp_end`变量在代码中扮演着当前处理片段的潜在终止位置的角色。在遍历字符串的过程中，如果遇到的字符在之前的字符的最后出现位置之前，我们就更新`temp_end`为当前字符的最后出现位置和已知的`temp_end`之间的较大值。这个更新过程确保了当前片段包含了所有必须在这个片段结束之前处理的字符。当遍历的当前位置`i`达到了`temp_end`时，说明没有更多字符需要包含在当前片段中，因此可以结束这个片段并将其长度记录下来，然后开始新的片段。
当`i`等于`temp_end`时，表明当前字符是当前片段的最后一个字符，因为`temp_end`是这个片段中所有字符的最后出现位置的最大值。在这种情况下，代码将当前片段的长度计算出来并加入到结果数组中，然后`i`增加1以开始新的片段。这个逻辑确实保证了每个字符只在一个片段中出现，因为每个片段的界定基于字符的最后出现位置，确保了字符不会在后续的片段中再次出现。
代码中的第一次遍历用于构建`end`哈希表，确定每个字符的最后出现位置；而第二次遍历则是基于这些信息来确定片段的边界。理论上，如果我们在第一次遍历时同时维护一个实时更新的`temp_end`，则可能在一个遍历中完成任务。然而，这样做可能需要更复杂的逻辑来同时处理字符最后出现位置的记录和片段的确定。实际上，两次遍历的方法因其清晰和易于理解的逻辑而更常用，尽管在某些情况下，合并为一次遍历可能略微提高效率。