763. Partition Labels

這題跟jump 幾乎一模一樣, 就是看第一個英文字母最遠到哪還會出現, 然後在遍歷到那個最遠的字母時, 其他字母會不會有更遠值,

若沒有了, 就可以形成一個group

這比較難是每次要處理這種index的問題都會很不熟練

class Solution {
public:
    vector<int> partitionLabels(string S) {
        vector<int> last(26,0);
        for(int i=0;i<S.size();i++) 
            last[S[i]-'a']=i;
        
        vector<int> res;
        int j=0,k=0;
        for(int i=0;i<S.size();i++) {
            j = max(j, last[S[i]-'a']);
            if(i==j) {
                res.push_back(i-k+1);
                k=i+1;
            }
        }
        return res;
    }
};