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

a -> 8
b -> 5
c -> 7
d -> 14
e -> 15
f -> 11
g -> 13
h -> 19
i -> 22
j -> 23
k -> 20
l -> 21

``````class Solution {
public:
vector<int> partitionLabels(string S) {
vector<int> res;
int n = S.size(), start = 0, last = 0;
unordered_map<char, int> m;
for (int i = 0; i < n; ++i) m[S[i]] = i;
for (int i = 0; i < n; ++i) {
last = max(last, m[S[i]]);
if (i == last) {
res.push_back(i - start + 1);
start = i + 1;
}
}
return res;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/763

Merge Intervals

https://leetcode.com/problems/partition-labels/

https://leetcode.com/problems/partition-labels/discuss/113259/Java-2-pass-O(n)-time-O(1)-space-extending-end-pointer-solution

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation