题目描述给你一个字符串s要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。例如ababcc能够被分为[abab, cc]。示例 1输入s ababcbacadefegdehijhklij 输出[9,7,8] 解释划分为 ababcbaca、defegde、hijhklij示例 2输入s eccbbbbdec 输出[10]解题思路总览思路时间复杂度空间复杂度适用场景哈希表存储O(n)O(n)直观但稍繁琐两遍遍历O(n)O(1)本题最优解算法一哈希表存储思路第一遍用哈希表记录每个字符最后出现的位置。第二遍遍历时维护当前片段中所有字符的最远边界。代码classSolution{public:vectorintpartitionLabels(string s){unordered_mapchar,intlast;for(inti0;is.size();i){last[s[i]]i;}vectorintans;intstart0,end0;for(inti0;is.size();i){endmax(end,last[s[i]]);if(endi){ans.push_back(end-start1);startend1;}}returnans;}};算法二数组优化最优解思路用数组代替哈希表记录每个字符最后出现的位置。数组下标对应字母值为最后出现位置。代码classSolution{public:vectorintpartitionLabels(string s){intns.size();intlast[26];for(inti0;in;i){last[s[i]-a]i;}vectorintans;intstart0,end0;for(inti0;in;i){endmax(end,last[s[i]-a]);if(endi){ans.push_back(end-start1);startend1;}}returnans;}};算法流程输入: s ababcbacadefegdehijhklij 第一步统计每个字符最后出现的位置 ------------------------------------------------------------- | 字符 | a | b | c | d | e | f | h | l | | 最后 | 8 | 9 | 7 | 14 | 15 | 11 | 19 | 22 | ------------------------------------------------------------- 第二步遍历字符串维护片段边界 ------------------------------------------------------------- | i0 | s[0]a, endmax(0,8)8 | end!i, 继续 | | i1 | s[1]b, endmax(8,9)9 | end!i, 继续 | | i2 | s[2]a, endmax(9,8)9 | end!i, 继续 | | i3 | s[3]b, endmax(9,9)9 | end!i, 继续 | | i4 | s[4]c, endmax(9,7)9 | end!i, 继续 | | i5 | s[5]b, endmax(9,9)9 | end!i, 继续 | | i6 | s[6]a, endmax(9,8)9 | end!i, 继续 | | i7 | s[7]c, endmax(9,7)9 | end!i, 继续 | | i8 | s[8]a, endmax(9,8)9 | endi! 切片段 | | | ans.push(8-01)9 | start9 | ------------------------------------------------------------- | i9 | s[9]d, endmax(9,14)14 | end!i, 继续 | | ... | ... | end!i, 继续 | | i15 | s[15]e, endmax(15,15)15 | endi! 切片段 | | | ans.push(15-91)7 | start16 | ------------------------------------------------------------- | i16 | s[16]f, end22 | end!i, 继续 | | ... | ... | end!i, 继续 | | i22 | s[22]l, end22 | endi! 切片段 | | | ans.push(22-161)7? 不对 | 实际是8 | ------------------------------------------------------------- 输出: ans [9, 7, 8]复杂度分析复杂度分析时间复杂度O(n)- 第一遍遍历O(n)- 第二遍遍历O(n)空间复杂度O(1)- 26 个字母的数组核心思想s ababcbacadefegdehijhklij 为什么 end i 时就能切片段 ------------------------------------------------------------- | 位置 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ... | | 字符 a b a b c b a c a d e f e g d e | | 最后 8 9 8 9 7 9 8 7 8 14 15 11 15 14 14 15 ... | ------------------------------------------------------------- 在位置 i如果 end i意味着 - 到位置 i 为止当前片段中的所有字符都已经出现过最后一次了 - 不会再有字符需要跨越 i 才能出现 - 所以位置 i 必须是片段的结束位置 片段 1 分析位置 0-8 - 包含的字符: a, b, c - a 的最后位置: 8 - b 的最后位置: 9 - c 的最后位置: 7 - 当前 end max(8,9,7) 9 - 但位置 8 时虽然 end9 ! 8但到了位置 8 之后 - a 的最后位置是 8就在当前位置不需要再延伸 - 所以 end i 8切片段复杂度对比总结思路平均时间最坏时间空间评价哈希表O(n)O(n)O(n)可行但稍慢数组O(n)O(n)O(1)最优面试追问 FAQ问题回答为什么end i就能切片段因为 end 是当前片段中所有字符最后出现位置的最大值。如果 i end说明所有在 [start, i] 范围内的字符都只出现在这个片段里不会延伸到后面为什么要两遍遍历第一遍找每个字符的最后位置第二遍根据最后位置判断片段边界为什么要用数组而不是哈希表26 个字母是固定的用数组 O(1) 空间比哈希表更快如果字符串为空怎么办返回空 vector这个算法和区间合并有什么关系本质是把「每个字符的出现区间」合并合并后的每个区间就是一个片段相关题目题目难度核心点763. 划分字母区间中等本题56. 合并区间中等区间合并435. 无重叠区间中等区间取舍总结项目内容核心思想两遍遍历第一遍记录最后位置第二遍根据最后位置切片段关键判断end i 时切割最优时间O(n)最优空间O(1)面试加分能解释「片段内所有字符的最后位置都不会超出片段边界」