题目描述

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。

样例

输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。

C++ 代码

题目的本质就是区间合并。
先用unordered_map<char, int>找出字符串中所有的字符
然后通过S.find()和S.rfind()方法找出每种字符的左右区间
最后对这些区间进行区间合并
合并出来的结果就是最终答案

需要知识：
    算法基础课 
        第一讲 基础算法
            区间合并
            https://www.acwing.com/problem/content/805/

class Solution {
public:
    vector<int> partitionLabels(string S) {
        unordered_map<char, int> um;
        for(int i = 0; i < S.size(); i ++)
        {
            um[S[i]] ++;
        } 

        vector<pair<int, int>> segs;
        for(auto item : um)
        {
            int l = S.find(item.first);
            int r = S.rfind(item.first);
            segs.push_back({l, r});
        }

        merge(segs);

        vector<int> res;
        for(int i = 0; i < segs.size(); i ++)
        {
            res.push_back(segs[i].second - segs[i].first + 1);
        }

        return res;
    }

    void merge(vector<pair<int, int>>& segs)
    {
        vector<pair<int, int>> res;

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

        int st = -2e9, ed =-2e9;
        for(auto seg : segs)
        {
            if(ed < seg.first)
            {
                if(st != -2e9)
                    res.push_back({st, ed});
                st = seg.first, ed = seg.second;
            }
            else
                ed = max(ed, seg.second);
        }

        if(st != -2e9)
            res.push_back({st, ed});

        segs = res;
    }
};