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
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.
题意： 给一个字符串，问最多能分成多少个 substring， 每个字母仅出现在同一个 substring 中。并且输出每个字串的长度。
这题和 jump II 很像。都要维护一个范围使每个字母都在同一个范围之内。 因此，我们可以开一个数组，来记录每一个字母最后出现的位置。这样遍历一下数组，并且设置一个变量 $j$ 来记录当前出现过的字母的最远位置。如果 $i$ 和 $j$ 相等的话，说明此 substring 已经包含了出现过的所有字符。 起始位置就可以往后面挪一位了。
代码
class Solution {
public List<Integer> partitionLabels(String S) {
int[] last = new int[26];
for(int i = 0; i < S.length(); i++) {
last[S.charAt(i) - 'a'] = i;
}
int j = 0, start = 0;
List<Integer> ret = new ArrayList<>();
for(int i = 0; i < S.length(); i++) {
j = Math.max(j,last[S.charAt(i) - 'a']);
if(i == j) {
ret.add(i-start+1);
start = i+1;
}
}
return ret;
}
}