1、题目来源
2、题目描述
给你一个字符串 s
。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。
注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是 s
。
返回一个表示每个字符串片段的长度的列表。
示例 1:
输入:s = "ababcbacadefegdehijhklij" 输出:[9,7,8] 解释: 划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的,因为划分的片段数较少。
示例 2:
输入:s = "eccbbbbdec" 输出:[10]
提示:
1 <= s.length <= 500
s
仅由小写英文字母组成
3、题解分享
class Solution {
public List<Integer> partitionLabels(String s) {
//思路:贪心 + 使用数组记录每个字母出现的最后位置,定义变量维护当前段所包含的字母的最远位置,一旦超出最远位置就记录一个答案,并开始下一段的遍历。
int[] tab = new int[26];
char[] chars = s.toCharArray();
int len = s.length();
for(int i = 0;i < len;++i){
tab[chars[i] - 'a'] = i;
}
List<Integer> ans = new ArrayList<>();
int curIndex = 0;
int leftIndex = 0;
int rightIndex = 0;
while(curIndex < len){
if(curIndex > rightIndex){
ans.add(rightIndex - leftIndex + 1);
leftIndex = curIndex;
}
rightIndex = Math.max(tab[chars[curIndex] - 'a'],rightIndex);
++curIndex;
}
ans.add(curIndex - leftIndex);
return ans;
}
}