题解 | #分品种# 贪心

知识点

贪心

思路

由于需要分割出更多的组，我们先预处理出每个字母出现的最后一个位置。之后我们指定一个开头，遍历从开头到当前字母的最后的位置（必须包含的位置），随着我们向后遍历会逐渐遇到新的字母，会把至少应该包含的末尾向后移动，直到我们遍历到末尾之后，就可以形成一个分割。之后加入答案即可。

时间复杂度

AC Code（C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型vector
     */
    vector<int> partitionLabels(string s) {
        int n = s.size();
        vector<int> pos(26, -1);
        for (int i = 0; i < n; i ++) {
            pos[s[i] - 'a'] = i;
        }
        vector<int> res;
        int st = 0;
        while (st < n) {
            int ed = pos[s[st] - 'a'];
            int x = st + 1;
            while (x < ed) {
                ed = max(ed, pos[s[x ++] - 'a']);
            }
            res.push_back(ed - st + 1);
            st = ed + 1;
        }
        return res;
    }
};