• 注册
• # 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.

```# Greedy solution
# Time complexity - O(n) | Space complexity - O(1)
def partitionLabels(self, S: str) -> List[int]:
# Store the last occurence of every character
loccur = {c:i for i,c in enumerate(S)}

anchor,currend,res = 0,0,[]
# For every character of the string, greedily check its last occurence and add it to res.
# Add the current partition corresponding to a character only when you're at the index which is the last occurence of that character.
for curr,c in enumerate(S):
# Expand the bounds of current partition based on farthest bound so far and current character's bound.
currend = max(currend,loccur[c])
# If current position is same as position of the farthest bound of characters so far, add it to the result and reset the anchor to the next element
if currend == curr:
res.append(currend-anchor+1)
anchor = curr + 1

return res```

请登录之后再进行评论

WordPress后台-外观-小工具 进行配置小工具

• 做任务
• 全部清空
•   