<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 bool sortcol(const vector<int>& v1, const vector<int>& v2)
    {
        return v1[1] < v2[1];
    }
    vector<string> maxNumOfSubstrings(string s) {
        vector<vector<int>> vec(26);
        int n=s.size();
        for(int i=0;i<n;i++){
            int ind=s[i]-'a';
            if(vec[ind].empty()||vec[ind].size()==1){
                vec[ind].push_back(i);
            }
            else{
                vec[ind].pop_back();
                vec[ind].push_back(i);
            }
        }
        for(int i=0;i<26;i++){
            if(vec[i].size()==1){
                vec[i].push_back(vec[i][0]);
            }
        }
        set<pair<int,int>> st;
        for(int i=0;i<26;i++){
            if(vec[i].empty()) continue;
            int sind=vec[i][0];
            int eind=vec[i][1];
            bool x=0;
            for(int j=sind;j<=eind;j++){
                int y=s[j]-'a';
                if(vec[y][0]<sind){
                    x=1;
                    break;
                }
                if(vec[y][1]>eind){
                    eind=vec[y][1];
                }
            }
            if(x==0){
                st.insert({sind,eind});
            }
        }
        vec.clear();
        for (auto& str : st) {
            vec.push_back({str.first, str.second});
        }
        sort(vec.begin(), vec.end(), sortcol);
        int m=vec.size();
        vector<vector<int>> temp[m];
        int maxi=0;
        for(int i=0;i<m;i++){
            int k=1;
            temp[i].push_back(vec[i]);
            for(int j=i+1;j<m;j++){
                if(vec[j][0]>temp[i].back()[1]){
                    temp[i].push_back(vec[j]);
                    k++;
                }
            }
            maxi=max(maxi, k);
        }
        int ind=0, mini=n+1;
        for(int i=0;i<m;i++){
            if(temp[i].size()==maxi){
                int tt=0;
                for(int j=0;j<temp[i].size();j++){
                    tt+=(temp[i][j][1]-temp[i][j][0]+1);
                }
                if(tt<mini){
                    ind=i;
                    mini=tt;
                }
            }
        }
        vector<string> ans;
        for(int i=0;i<temp[ind].size();i++){
            string ss=s.substr(temp[ind][i][0],temp[ind][i][1]-temp[ind][i][0]+1 );
            ans.push_back(ss);
        }
        return ans;
    }
};
25795