<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:
    struct cmp {
        bool operator()(string a, string b) const {
            if(a.length() == b.length())
                return a<b;
            else 
                return a.length() < b.length(); 
        }
    };

    int f1=-1,l1=-1;

    string prepareAgain(vector<vector<int>> &occurence, string s, int i){
        int firstInd = occurence[i][0];
        int lastInd = occurence[i][1];
        int firstTemp = firstInd, lastTemp = lastInd;

                for(int j= firstTemp;j<=lastTemp;j++){
                    char c_ind = s[j] - 'a';
                    int mid1 = occurence[c_ind][0], mid2 = occurence[c_ind][1];
                    if(mid1 != -1 && mid1<firstInd){
                        firstInd = mid1;
                    }
                    if(mid2 > lastInd)
                        lastInd = mid2;
                }

        occurence[i][0] = firstInd;
        occurence[i][1] = lastInd;
        f1=firstInd; l1 = lastInd;
        return s.substr(firstInd, lastInd-firstInd+1);
    }

    vector<string> maxNumOfSubstrings(string s) {
        vector<vector<int>> occurence(26,{-1,-1});

        for(int i=0;i<s.length();i++){
            char c = s[i];
            int ind = c-'a';

            if(occurence[ind][0] == -1){
                occurence[ind][0] = i;
                occurence[ind][1] = i;
            }else{
                occurence[ind][1] = i;
            }
        }

        map<string,vector<int>,cmp> mp;

        for(int i=0;i<26;i++){
            int firstInd = occurence[i][0];
            int lastInd = occurence[i][1];

            if(firstInd != -1 && lastInd != -1){
                string sub = s.substr(firstInd, lastInd-firstInd+1);
                

                sub = s.substr(firstInd, lastInd-firstInd+1);
                string x = prepareAgain(occurence,s,i);
                
                while(sub != x){
                    sub = x;
                    x = prepareAgain(occurence,s,i);
                }
                
                if(f1!=-1 && l1!=-1){
                    firstInd = f1;
                    lastInd = l1;
                    f1=-1;
                    l1=-1;
                }
                mp[sub].push_back(firstInd);
                mp[sub].push_back(lastInd);
            }
        }

        vector<bool> covered(s.length(),0);

        vector<string> ans;

        for(auto i=mp.begin();i!=mp.end();i++){
            string temp = i->first;
            vector<int>occ = i->second;
            
            int flag = 0;

            for(int j=occ[0];j<=occ[1];j++){
                if(covered[j]){
                    flag=1;
                    break;
                }
            }

            if(!flag){
                for(int j=occ[0];j<=occ[1];j++){
                    covered[j] = 1;
                }

                ans.push_back(temp);
            }
            
        }
        return ans;

    }
};
156345