<p>Given a string <code>s</code> of lowercase letters, you need to find the maximum number of <strong>non-empty</strong> substrings of <code>s</code> that meet the following conditions:</p>

<ol>
	<li>The substrings do not overlap, that is for any two substrings <code>s[i..j]</code> and <code>s[x..y]</code>, either <code>j &lt; x</code> or <code>i &gt; y</code> is true.</li>
	<li>A substring that contains a certain character <code>c</code> must also contain all occurrences of <code>c</code>.</li>
</ol>

<p>Find <em>the maximum number of substrings that meet the above conditions</em>. If there are multiple solutions with the same number of substrings, <em>return the one with minimum total length. </em>It can be shown that there exists a unique solution of minimum total length.</p>

<p>Notice that you can return the substrings in <strong>any</strong> order.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;adefaddaccc&quot;
<strong>Output:</strong> [&quot;e&quot;,&quot;f&quot;,&quot;ccc&quot;]
<b>Explanation:</b>&nbsp;The following are all the possible substrings that meet the conditions:
[
&nbsp; &quot;adefaddaccc&quot;
&nbsp; &quot;adefadda&quot;,
&nbsp; &quot;ef&quot;,
&nbsp; &quot;e&quot;,
  &quot;f&quot;,
&nbsp; &quot;ccc&quot;,
]
If we choose the first string, we cannot choose anything else and we&#39;d get only 1. If we choose &quot;adefadda&quot;, we are left with &quot;ccc&quot; which is the only one that doesn&#39;t overlap, thus obtaining 2 substrings. Notice also, that it&#39;s not optimal to choose &quot;ef&quot; since it can be split into two. Therefore, the optimal way is to choose [&quot;e&quot;,&quot;f&quot;,&quot;ccc&quot;] which gives us 3 substrings. No other solution of the same number of substrings exist.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;abbaccd&quot;
<strong>Output:</strong> [&quot;d&quot;,&quot;bb&quot;,&quot;cc&quot;]
<b>Explanation: </b>Notice that while the set of substrings [&quot;d&quot;,&quot;abba&quot;,&quot;cc&quot;] also has length 3, it&#39;s considered incorrect since it has larger total length.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>
	<li><code>s</code> contains only lowercase English letters.</li>
</ul>

class Solution {
public:
    static const bool f(const pair<int,int>&v1,const pair<int,int>&v2){
        return (v1.second-v1.first<v2.second-v2.first);
    }
    vector<string> maxNumOfSubstrings(string s) {
        vector<pair<int,int>>v(26,{-1,-1});
        for(int i=0;i<s.size();i++){
            int ch=s[i]-'a';
            if(v[ch].first==-1) v[ch]={i,i};
            else{
                v[ch].second=i;
            }
        }
       // sort(v.begin(),v.end(),f);
        //for(auto it:v) cout<<it.first<<" "<<it.second<<endl;
        vector<string>res;
        set<int>st;
        // for(int k=0;k<26;k++){
        // for(int i=0;i<26;i++){
        //     for(int j=0;j<26;j++){
        //         if(v[j].first>=v[i].first && v[j].first<=v[i].second)
        //         v[i].second=max(v[i].second,v[j].second);
        //         if(v[j].second<=v[i].second && v[j].second>=v[i].first)
        //         v[i].first=min(v[i].first,v[j].first);
        //     }
        // }
        // }
        for(int l=0;l<26;l++){
        for(int i=0;i<26;i++){
            if(v[i].first==-1) continue;
            else{
                for(int k=v[i].first;k<=v[i].second;k++){
                    int j=s[k]-'a';
                    v[i].first=min(v[i].first,v[j].first);
                    v[i].second=max(v[i].second,v[j].second);
                }
            }
        }
        }
        sort(v.begin(),v.end(),f);
        for(int i=0;i<26;i++){
            if(v[i].first==-1) continue;
            else{
                if(!st.size()){
                    res.push_back(s.substr(v[i].first,v[i].second-v[i].first+1));
                    for(int j=v[i].first;j<=v[i].second;j++){
                        st.insert(j);
                    }
                    continue;
                }
                auto it=st.lower_bound(v[i].first);
                if(it==st.end() || ((*it)>v[i].second)){
                    res.push_back(s.substr(v[i].first,v[i].second-v[i].first+1));
                    for(int j=v[i].first;j<=v[i].second;j++){
                        //cout<<j<<" ";
                        st.insert(j);
                    }
                }
            
            }
        }
        return res;
        
    }
};
89205