前言

今天要解的題目是top 100 liked裡面的763. Partition Labels這題~ 這題的tag包含hash table, two pointers, string及greedy，一起來看看怎麼解吧！

想法

首先這個題目可以重新整理一下，變成更單純的題目條件。題目要求是string的切分方法要讓每個character只出現在其中一個substring，所以其實就=每個字母第一次出現跟最後一次出現要被劃分在同一個substring中。
而因為之前寫過56. Merge Intervals這題，所以我非常直覺地把這題轉換成那題的邏輯來看，拆分成兩大部分：

1. 列出每個字母第一次出現/最後一次出現的位置
2. 變成merge intervals題目─若interval與interval之間有交錯，就進行融合

而merge intervals的解法則很簡單：按照每個intervals的start進行排列，之後遍歷比較後面每個intervals的start是否有早於前面intervals的end，若沒有就可以直接新增新的intervals在後面(不須融合)，而若有則更新目前interval的end。

採用這個邏輯，整個程式碼如下：

class Solution {
public:
    vector<int> partitionLabels(string s) {
        // turn each character first appears and last appears into intervals
        // save the appearing order of characters
        unordered_map<char, int> seen;
        vector<pair<int, int>> intervals;
        int idx=0;
        for(int i=0;i<s.length();++i){
            // not seen, initial the interval
            if(!seen.count(s[i])){
                intervals.push_back({i,i});
                seen[s[i]]=idx;
                ++idx;
            }
            // seen, update the last position
            else{
                intervals[seen[s[i]]].second=i;
            }
        }
        // if interval not overlapped, add the partition
        vector<int> ans;
        int last=intervals[0].second;
        int start=intervals[0].first;
        for(int i=1; i<intervals.size();++i){
            if(intervals[i].first>last){
                ans.push_back(last-start+1);
                start = intervals[i].first;
                last = intervals[i].second;
            }else{
                last=max(last, intervals[i].second);
            }
            
        }
        ans.push_back(last-start+1);
        return ans;
        
    }
};

而我也看到不少其他人寫法是比較單純的方式，沒有轉換那麼多層，也可以參考看看，摘錄其中一個解答如下(新增了一些註解部分)：

class Solution {
public:
    vector<int> partitionLabels(string S) {
        // save the last position of each character
        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;
        // iterate over the string again
        for(int i=0;i<S.size();i++) {
            // update the end of current interval(max of current end and the current charater last appear position)
            j = max(j, last[S[i]-'a']);
            // if this interval can end at this position, add the partition
            if(i==j) {
                res.push_back(i-k+1);
                k=i+1;
            }
        }
        return res;
    }
};

以上時間複雜度都為O(n)，對整個string進行遍歷2次。

結語

連假已結束~ 好好把這下半個月拚完吧！