763. Partition Labels

#### QUESTION:

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.

#### EXPLANATION:

1.首先算出每个字符最后出现的位置，这样可以知道每次这个字符出现，都必须要划线到那个位置
2.进行循环，依次查看最后出现的位置，并标记最后的位置
3.如果当前的位置就是最后的位置，因为需要分成尽可能多的位置，那么就可以将该位置进行切割
4.最后再计算每一段的长度

#### SOLUTION:

``````class Solution {
public List<Integer> partitionLabels(String S) {
int[] count = new int[26];
char[] chars = S.toCharArray();
for(int i = 0;i<chars.length;i++) count[chars[i]-'a'] = i;
ArrayList<Integer> index = new ArrayList<>();
int last = count[chars[0]-'a'];
for(int i = 0;i<chars.length;i++){
last = Math.max(last,count[chars[i]-'a']);