### 题目

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:

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

### 关键在于找出每个字母的出现范围

a a   a
| |   |
|
|------|
|
最早从这里切


#### 代码

class Solution {
public List<Integer> partitionLabels(String S) {
List<Integer> res = new ArrayList<>();
int[] table = parse(S);
int p = 0, size = S.length();
while (p < size) {
int start = p, scope = p;
while (p < size && p <= scope) {
int newScope = table[S.charAt(p) - 'a'];
if (newScope > scope) scope = newScope;
p++;
}
}
return res;
}

private int[] parse(String S) {
int[] table = new int[26];
for (int i = 0; i < S.length(); i++) {
char c = S.charAt(i);
table[c - 'a'] = i;
}
return table;
}
}