题目要求：

给定一个字符串，要求把它切割成最小子字符串的集合，使得每一个字母只可能出现在一个子字符串中。举例如下：若给定字符串s = ‘aaabbccabnnmmng’，期待的输出结果为[[0, 8], [9, 13], [14, 14]]。因为切分后的字符串为：res = ['aaabbccab','nnmmn','g'].

解题思路：

我自己花了几个小时都没有做出来，是一位大佬告诉我他的思路，这里总结如下：
需要找到每个字母出现的第一个位置和最后一个位置，然后再取区间的最大并集即可。

解题步骤：

首先是用一个函数 get_position来找出每个字母出现的第一个位置和最后一个位置。代码如下：

def get_position(s):
    position_start = dict()
    position_end = dict()
    for i in range(len(s)):
        position_end.update({s[i]:i})
    for i in range(len(s)):
        if position_start.get(s[i],'') == '':
            print(i)
            position_start.update({s[i]:i})
    position = []
    for key in position_start:
        position.append([position_start[key],position_end[key]])
    return position

如果输入目标字符串‘'aaabbccabnnmmng'，这个函数的输出为：

[[0, 7], [3, 8], [5, 6], [9, 13], [11, 12], [14, 14]]

也就是每一个字母出现的起始位置。

下一步需要给这些区间取并集，其实画在数轴上是一个比较容易理解的办法，但是如果想要让程序也能识别，可以使用条件：

• 如果一个区间的右边界小于另一个区间的左边界，则两个区间没有交集。
• 如果一个区间的左边界小于另一区间左边界，右边界大于另一个区间的右边界，则第一个区间一定包含第二个区间。

从上面两个规则就可以得到区间合并的函数：

from typing import List

def string_cut(string:str)->List[List[int, int]]:
    position = get_position(string) # 调用上面得到每个字母的首尾的函数
    i = 0
    result = []
    for i in position:
        if not result or result[-1][1] <i[0]:
            result.append(i)
            continue
        if result[-1][1] <i[1]:
            result[-1][1] = i[1]
    return result