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:

1
2
3
4
5
6
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.

从前往后和从后往前遍历一遍数组,对于每一个元素,记录它之前(含自己)和之后(含自己)每个字符出现的个数。然后再遍历一次,每一个字符都没有在某下标之前和之后都出现,那么这个下标就可以用来分割。注意结尾的corner case。

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
vector<int> partitionLabels(string S) {
vector<vector<int>> front, back;
vector<int> v(26, 0);
for (int i = 0; i < S.length(); i++) {
char ch = S[i];
v[ch - 'a']++;
front.push_back(v);
}

v.assign(26, 0);
for (int i = S.length() - 1; i >= 0; i--) {
char ch = S[i];
v[ch - 'a']++;
back.push_back(v);
}

reverse(back.begin(), back.end());

vector<int> ans;
int prev = 0;

for (int i = 0; i < S.length() - 1; i++) {
bool flag = true;
for (int j = 0; j < 26; j++) {
if (!(front[i][j] == 0 || back[i + 1][j] == 0)) {
flag = false;
break;
}
}

if (flag) {
ans.push_back(i + 1 - prev);
prev = i + 1;
}
}

if (prev != S.length()) {
ans.push_back(S.length() - prev);
}

return ans;
}

};