时间复杂度O(N) 空间复杂度O(N)
只需要遍历两遍字符串，第一遍用hash表统计每个字母出现的最大下标。就是最晚出现的下标。 第二遍分段，每一段都记录一个left，right就是当前下标。用一个max_ind记录当前段遍历过的最大下标，如果当前坐标等于最大下标，就开始下一段的记录。并把当前的结果加入ans结果集。 [盗一下大佬的图片。]
# 字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。 # # # # 示例 1： # # 输入：S = "ababcbacadefegdehijhklij" # 输出：[9,7,8] # 解释： # 划分结果为 "ababcbaca", "defegde", "hijhklij"。 # 每个字母最多出现在一个片段中。 # 像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。 # # # # # 提示： # # # S的长度在[1, 500]之间。 # S只包含小写字母 'a' 到 'z' 。 # # Related Topics 贪心算法 双指针 # 👍 330 👎 0 # 763.划分字母区间 # leetcode submit region begin(Prohibit modification and deletion) from typing import List class Solution: def partitionLabels(self, S: str) -> List[int]: ans = [] my_map = {} max_ind = 0 right = 0 left = 0 for indexi,i in enumerate(S): my_map[i] = indexi # dic = {s: index for index, s in enumerate(S)} for indexi,i in enumerate(S): max_ind = max(max_ind, my_map[S[indexi]]) if indexi == max_ind: ans.append(indexi-left+1) left = indexi + 1 return ans if __name__ == '__main__': sol = Solution() sol.partitionLabels("ababcbacadefegdehijhklij")