Leetcode763: 划分字母区间

题目连接🔗
https://leetcode-cn.com/problems/partition-labels/

题目描述🗒
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。

image.png

思路💡

1. 遍历字符串，统计每一个字母最后出现的index
2. 再次遍历， 使用双指针start 和 end， 维护end = 当前字母的最后出现字符（两者取最大值）
3. 进入下一轮的条件，当前字符就是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;
    }
};