LeetCode 1520. 最多的不重叠子字符串（贪心）

示例 1：
输入：s = "adefaddaccc"
输出：["e","f","ccc"]
解释：下面为所有满足第二个条件的子字符串：
[
  "adefaddaccc"
  "adefadda",
  "ef",
  "e",
  "f",
  "ccc",
]
如果我们选择第一个字符串，那么我们无法再选择其他任何字符串，所以答案为 1 。
如果我们选择 "adefadda" ，剩下子字符串中我们只可以选择 "ccc" ，
它是唯一不重叠的子字符串，所以答案为 2 。
同时我们可以发现，选择 "ef" 不是最优的，因为它可以被拆分成 2 个子字符串。
所以最优解是选择 ["e","f","ccc"] ，答案为 3 。
不存在别的相同数目子字符串解。

示例 2：
输入：s = "abbaccd"
输出：["d","bb","cc"]
解释：注意到解 ["d","abba","cc"] 答案也为 3 ，但它不是最优解，因为它的总长度更长。
 
提示：
1 <= s.length <= 10^5
s 只包含小写英文字母。

class Solution {
public:
    vector<string> maxNumOfSubstrings(string s) {
    	vector<int> start(26,-1), end(26,-1);
    	int i = 0, n = s.size(), l, r, last = -1;
    	for(i = 0; i < n; ++i)
    	{
    		char ch = s[i];
    		if(start[ch-'a'] == -1)
    			start[ch-'a'] = i;
    		end[ch-'a'] = i;
    	}
    	vector<int> endpos;
    	for(auto e : end)
    		if(e != -1)
    			endpos.push_back(e);
    	sort(endpos.begin(), endpos.end());
    	vector<string> ans;
    	for(auto e : endpos)
    	{
    		l = start[s[e]-'a'];
    		r = e;
    		while(l < r)
    		{
    			if(end[s[r]-'a'] > e || l <= last)
    				break;
    			l = min(l, start[s[r]-'a']);
    			r--;
    		}
    		if(r == l)
    		{
                ans.push_back(s.substr(l, e-l+1));
                last = e;
            }
    	}
    	return ans;
    }
};