## 题目描述：

LeetCode 763. Partition Labels

A string `S` of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1:

```Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.
```

Note:

1. `S` will have length in range `[1, 500]`.
2. `S` will consist of lowercase letters (`'a'` to `'z'`) only.

## 解题思路：

```由于S只包含字母a - z，因此按照字母统计出现的最小、最大位置。

## Python代码：

``````class Solution(object):
def partitionLabels(self, S):
"""
:type S: str
:rtype: List[int]
"""
rangeDict = {}
for i, c in enumerate(S):
if c not in rangeDict: rangeDict[c] = [i, i]
else: rangeDict[c][1] = i
rangeList = sorted(rangeDict.values(), cmp = lambda x, y: x[0] - y[0] or y[1] - x[1])
ans = []
cmin = cmax = 0
for start, end in rangeList:
if start > cmax:
ans.append(cmax - cmin + 1)
cmin, cmax = start, end
else: cmax = max(cmax, end)
ans.append(cmax - cmin + 1)
return ans
``````

Pingbacks已关闭。

1. ks864148379 发布于 2018年1月19日 15:49 #

题目好像是翻译错了。。。求的不是最少的区间，是最多的区间

2. 在线疯狂 发布于 2018年1月20日 14:50 #

感谢指正，已经修改 :)

3. Mark 发布于 2018年5月19日 10:12 #

第11行，应该只需要按起点升序就行了