Leetcode763.划分字母区间

763. 划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：

1
2
3
4
5
6
>输入：s = "ababcbacadefegdehijhklij"
>输出：[9,7,8]
>解释：
>划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
>每个字母最多出现在一个片段中。
>像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。

示例 2：

1
2
>输入：s = "eccbbbbdec"
>输出：[10]

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution(object):
    def partitionLabels(self, s):
        times = Counter(s)   # 统计每一个字符出现的次数
        # 例如times = Counter({u'b': 4, u'c': 3, u'e': 2, u'd': 1})
        res = []
        hashset = set()
        count = 0

        for e in s:
            # 遍历并且记录当前位置出现的字符，每次出现就减少1
            # 并且在哈希表中添加该字符
            times[e] -= 1
            if times[e] > 0:
                hashset.add(e)   
            else:
                # 当times为0的时候，也即出现次数为0的时候，从记录的哈希表中删除该字符
                if e in hashset:
                    hashset.remove(e)
            count += 1
            # 所有可能出现过的字符都已经完全出现之后，将其分段
            # （所有出现过的字符 times=0，之后不会再出现）
            if not hashset:
                res.append(count)
                count = 0

        return res