[LeetCode] Partition Labels 分割标签

时间:2021-09-02 23:17:38

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的距离。