763

class Solution {
public:
    vector<int> partitionLabels(string S) {
        int last[26]={0};
        vector<int> res;

        for(int i=0; i<S.length(); i++)
            last[S[i]-'a'] = i;

        for(int i=0,left=0,right=0; i<S.length(); i++){
            right = max(last[S[i]-'a'], right);
            if(right == i){
                res.push_back(right-left+1);
                left = i+1;
            }
        }
        return res;
    }
};