[LeetCode] 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 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:

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

 

思路1：

　　用两个指针start，end遍历整个字符串，start到end部分是满足条件的子串。

　　再用一个指针i遍历从start到end的子串，不断更新end的位置。

 

思路2：

　　用指针i遍历整个字符串，保持last为最新的子串末尾位置，当i与last相等的时候，说明满足条件的子串出现了，记录start到last的距离。