LC 1520. Maximum Number of Non-Overlapping Substrings

link

class Solution {
public:
    vector<string> maxNumOfSubstrings(string s) {
        int n=s.size();
        vector<int> left(26,n);
        vector<int> right(26,-1);
        for(int i=0;i<n;i++){
            left[s[i]-'a']=min(left[s[i]-'a'],i);
            right[s[i]-'a']=max(right[s[i]-'a'],i);
        }
        vector<string> res;
        int currightB=-1;
        for(int i=0;i<n;i++){
            if(i!=left[s[i]-'a']) continue;
            int tmp=right[s[i]-'a'];
            for(int j=i+1;j<=tmp;j++){
                if(left[s[j]-'a']<i) {
                    tmp=-1;
                    break;
                }
                tmp=max(tmp,right[s[j]-'a']);
            }
            if(tmp==-1) continue;
            if(i>currightB){
                res.push_back(s.substr(i,tmp-i+1));
                currightB=tmp;
            }else{
                res.pop_back();
                res.push_back(s.substr(i,tmp-i+1));
                currightB=tmp;
            }
        }
        return res;
    }
};