• 注册
• 查看作者
• # 领扣：1045. Partition Labels

### 1045. 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

```Example 1:
Output:  [9,7,8]

Explanation:
The partitions are "ababcbaca", "defegde", "hijhklij".
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.

Example 2:
Input: S = "abcab"
Output:  

Explanation:
We can not split it.
```

### Notice

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

```class Solution:
"""
@param S: a string
@return: a list of integers representing the size of these parts
"""
def partitionLabels(self, S):
# Write your code here
last = {}
for each in range(len(S)):
last[S[each]] = each

start, end , i = 0,0,0
res = []
while i < len(S) and start < len(S):

i = start
end = last[S[start]]
while i < end:

end = max(end, last[S[i]])
i +=1
res.append(end-start +1)
start = end +1
return res```

Find the latest position that letter appears in the string, save it to the dictionary.

Go from the start point to the (max) lastest position it appears in the string.

until the interval, and save the length, and iterate to the next interval.

Until the start < length of the string, and return all the saved length of the partition.

We have to go over the string twice, the time complexity is O(2n) = O(n)

The most possible dictionary can go is 26, which constant. Space complexity is O(1)

纽约州·纽约
• 0
• 0
• 0
• 187