leetcode 763 - Partition Labels

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

A string S of lowercase English 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:

S will have length in range [1, 500].
S will consist of lowercase English letters (‘a’ to ‘z’) only.

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
27
28
29
class Solution {
public:
vector<int> partitionLabels(string S) {
vector<int> count(26, 0);

for (int c : S)
count[c-'a']++;

unordered_map<char, int> maps;

int prev = 0;

vector<int> result;

for (int i = 0; i < S.size(); i++) {
char c = S[i];

if (++maps[c] == count[c-'a'])
maps.erase(c);

if (maps.size() == 0) {
result.push_back(i - prev + 1);
prev = i + 1;
}
}

return result;
}
};