题目连接🔗
https://leetcode-cn.com/problems/partition-labels/
题目描述🗒
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。
image.png
思路💡
- 遍历字符串，统计每一个字母最后出现的index
- 再次遍历， 使用双指针start 和 end， 维护end = 当前字母的最后出现字符（两者取最大值）
- 进入下一轮的条件，当前字符就是end。则将start和end的长度更新到结果vector中，start和end往后进1 开始下一轮
代码✅
class Solution {
public:
vector<int> partitionLabels(string S) {
vector<int> record(26,0); //记录最后一个字符出现的位置
for(int i = 0; i < S.size();i++){
record[S[i] - 'a'] = i;
}
vector<int> res;
int start = 0;
int end = 0;
int cur = 0;
while(cur < S.size()){
//cout<<"end: "<<end<<endl;
end = max(end, record[S[cur] - 'a']);
if(cur == end){
res.push_back(end - start + 1);
end = end + 1;
start = end;
}
cur++;
}
return res;
}
};
