Leetcode 768 Solution

class Solution {
public:
    vector<int> partitionLabels(string S) {
        vector<pair<int, int>> a;
        a.resize(26);

        for (int i = 0; i < 26; i++)
            a[i] = make_pair(-1, -1);

        for (int i = 0; i < S.size(); i++)
        {
            int j = S[i] - 'a';
            if (a[j].first == -1)
                a[j].first = i;
            a[j].second = i;
        }

        sort(a.begin(), a.end());

        int start = -1;
        int end = -1;
        vector<int> ans;

        for (int i = 0; i < a.size(); i++)
        {
            if (a[i].first == -1)
                continue;

            if (start == -1)
            {
                start = a[i].first;
                end = a[i].second;
            }
            else if (a[i].second > end)
                end = a[i].second;

            if (i == a.size() - 1 || end < a[i + 1].first)
            {
                ans.push_back(end - start + 1);
                start = -1;
                end = -1;
            }
        }

        return ans;
    }
};