题目描述

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

示例

输入:S = "ababcbacadefegdehijhklij"
输出:[9,7,8]
解释:
划分结果为 "ababcbaca", "defegde", "hijhklij"
每个字母最多出现在一个片段中。
"ababcbacadefegde", "hijhklij" 的划分是错误的,因为划分的片段数较少。

题目解析

  1. 维护一个数组,子路字符串中每个字母最后一次出现的下标
  2. 维护两个变量start,end,遍历字符串,更新end
    1. end至少为前边字母出现位置最靠后的索引,因此end=Max(end,endc)
  3. 因为要求尽可能多的划分所以在遍历过程中只要碰到end = 当前遍历索引就可以直接截断,这样得到的片段是最小的因此,片数会多。
  4. 更新start = end + 1

Coding

class Solution {
public List<Integer> partitionLabels(String s) {
int n = s.length();
int[] last = new int[26];
for(int i = 0;i < n;i++){
int a = s.charAt(i) - 'a';
last[a] = i;
}
List<Integer> res = new ArrayList<>();
int start = 0;
int end = 0;
for(int i = 0;i < n;i++){
int a = s.charAt(i) - 'a';
end = Math.max(end,last[a]);
if(i == end){
res.add(end - start + 1);
start = end + 1;
}
}
return res;
}
}