问题描述

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

 

示例：

输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。

 

提示：

• S的长度在[1, 500]之间。
• S只包含小写字母 'a' 到 'z' 。

方法一（贪心+双指针）

解题思路

由于同一个字母只能出现在同一个片段，显然同一个字母的第一次出现的下标位置和最后一次出现的下标位置必须出现在同一个片段。因此需要遍历字符串，得到每个字母最后一次出现的下标位置。

想切割，要有首尾两个指针，确定了结尾指针，就能确定下一个切割的开始指针。
遍历字符串，如果已扫描部分的所有字符，都只出现在已扫描的范围内，即可做切割。

我们假设变量start和maxIndex为开始和结束的两个标记指针。由于上一步已经得到了每个字符出现的最后索引。所以变遍历每个字母的同时，边求得出现索引最远的字母。这样，就可以确保之前所有的字符的出现位置都小于索引出现最远的字母了。

如果当前位置i已经等于最远出现的字符索引，那么在这里就可以直接切割，使用maxIndex-start+1来求得每段分割的最长数量，从而达到最多的分割数。

上述做法使用贪心的思想寻找每个片段可能的最小结束下标，因此可以保证每个片段的长度一定是符合要求的最短长度，如果取更短的片段，则一定会出现同一个字母出现在多个片段中的情况。由于每次取的片段都是符合要求的最短的片段，因此得到的片段数也是最多的。

代码实现

class Solution:
    def partitionLabels(self, S: str) -> List[int]:
        mapping = {}
        for i,char in enumerate(S):
            mapping[char] = i
        start, maxIndex = 0, 0
        result = []
        for i,char in enumerate(S):
            maxIndex = max(maxIndex, mapping[char])
            if i == maxIndex:
                result.append(maxIndex-start+1)
                start = maxIndex+1
        return result

方法二（区间合并转换）

解题思路

这个问题的解题过程可以转化为求解区间合并的问题。

要求出字符出现的最远出现位置，可以把它看成这个字符出现区间的末端。而第一出现该字符的位置为头端。这样就构成了每个字符出现从开始到结束的区间范围，如下如所示：

那么从这个图中就可以受到区间合并的启发，可以看到要使同一字母最多出现在一个片段中，那么只要确保最远出现的字符的位置就可以了。最远出现字符的位置可以对小于其出现位置的字符区间进行合并，从而是原字符串分为三个颜色的分断。从图中很容易看出。

代码实现

class Solution:
    def partitionLabels(self, S: str) -> List[int]:
        intervals={}
        for i in range(len(S)):
            # 如果第一次出现就加入区间[i,i]
            if S[i] not in intervals:
                intervals[S[i]]=[i,i]
            # 如果已经出现过，就更新区间终点
            else:
                intervals[S[i]][1]=i
        # 把所有区间取出放入列表, 然后根据区间起点排序
        temp=list(intervals.values())
        temp.sort(key=lambda x:x[0])
        ans = []
        for i in range(len(temp)):
            # 不可能存在相等的情况，区间完全不相交，直接加上即可
            if not ans or ans[-1][1] < temp[i][0]:
                ans.append(temp[i])
            # 在区间重叠的情况下，如果终点更大，则更新
            elif temp[i][1] > ans[-1][1]:
                ans[-1][1] = temp[i][1]
        res=[x[1]-x[0]+1 for x in ans]              
        return res