1520. 最多的不重叠子字符串

1520. 最多的不重叠子字符串

贪心

class Solution {
public:
    struct Seg{
        int l,r;
        bool operator< (const Seg &s) const{
            if(r!=s.r)return r<s.r;
            return l<s.l;
        }
    };

    vector<string> maxNumOfSubstrings(string s) {
        vector<Seg>segs(26,(Seg){-1,-1});

        for(int i=0;i<s.size();i++){
            int c=s[i]-'a';
            if(segs[c].l==-1) segs[c].l=segs[c].r=i;
            segs[c].r=i;
        }

        for(int i=0;i<26;i++){
            if(segs[i].l!=-1){
                for(int j=segs[i].l;j<=segs[i].r;j++){
                    int c=s[j]-'a';
                    if(segs[i].l<=segs[c].l && segs[i].r>=segs[c].r)continue;
                    segs[i].l=min(segs[i].l,segs[c].l);
                    segs[i].r=max(segs[i].r,segs[c].r);
                    j=segs[i].l;
                }
            }
        }

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

        vector<string>res;
        int end=-1;
        for(int i=0;i<26;i++){
            int l=segs[i].l,r=segs[i].r;
            if(segs[i].l==-1)continue;
            if(end==-1 || l>end){
                res.push_back(s.substr(l,r-l+1));
                end=r;
            }
        }

        return res;
    }
};