题目

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

示例：

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

提示：
S的长度在[1, 500]之间。
S只包含小写字母 'a' 到 'z' 。

解题方法

贪心

同一个字母必须出现在同一个片段中，因此关键在于该字母最后一次出现的下标，通过一次遍历获取所有字母最后一次出现的下标。再次遍历数组，记录出现过的元素中最远的结束下标，当遍历的下标与该结束下标相等时，表明前面的所有字符在后续不会再出现，该下标即分割点，记录各片段长度即可。
C++代码：

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int last[26] = {0};
        for(int i=0; i<s.size(); i++) last[s[i]-'a'] = i;
        vector<int> result;
        int num = 0;
        int right = 0;
        for(int i=0; i<s.size(); i++) {
            num++;
            right = right > last[s[i]-'a'] ? right : last[s[i]-'a'];
            if(right==i) {
                result.push_back(num);
                num = 0;
            }
        }

        return result;
    }
};