<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 {
    void topoSort(stack<char> &s, char c, unordered_map<char, vector<char>> &adj, unordered_map<char, bool> &vis) {
        vis[c]=true;

        for(auto i:adj[c]){
            if(!vis[i])
                topoSort(s, i, adj, vis);
        }
        s.push(c);
    }
    void dfs(char c, vector<int> &batches, int &batch, vector<int> &degree, unordered_map<char, vector<char>> &adj) {
        if(batches[c-'a']<0){
            batches[c-'a']=batch;
            for(auto i:adj[c]){
                dfs(i, batches, batch, degree, adj);
            }
        } else if(batches[c-'a']!=batch){
            degree[batches[c-'a']]++;
        }
    }   
public:
    vector<string> maxNumOfSubstrings(string str) {
        vector<int> mins(26, INT_MAX), maxs(26, -1);
        // populating the first indices of chars in mins and last ones in maxs
        for(int i=0; i<str.size(); i++){
            int index = str[i]-'a';
            mins[index] = min(mins[index], i);
            maxs[index] = i;
        }
        unordered_map<char, vector<char>> adj;
        unordered_map<char, bool> vis;
        // populating the adjacency list:
        for(int i=0;i<26;i++){
            for(int j=mins[i]; j<=maxs[i]; j++){
                adj[i+'a'].push_back(str[j]);
            }
        }
        stack<char> s;
        // topological sort in stack s:
        for(char c='a'; c<='z'; c++){
            if(!vis[c])
                topoSort(s, c, adj, vis);
        }

        // transpose the map:
        unordered_map<char, vector<char>> transadj;
        for(auto i:adj){
            for(auto j:i.second){
                transadj[j].push_back(i.first);
            }
        }
        vis.clear();
       
        int scc = 0;
        vector<int> batches(26, -1); // scc number (batch) of each char
        vector<int> degree(26, 0); // outdegree of each scc

        while (!s.empty()) {
            char c = s.top();
            s.pop();

            if (batches[c-'a'] == -1) {
                dfs(c, batches, scc, degree, transadj);
                scc++;
            }
        }
        vector<string> ans;
        for(int i=scc-1; i>=0; i--){
            if(degree[i]==0){
                int mini=INT_MAX, maxi = -1;
                for(int j=0;j<26; j++){
                    if(batches[j]==i){
                        mini = min(mini, mins[j]);
                        maxi = max(maxi, maxs[j]);
                    }
                }
                if(mini!=INT_MAX && maxi!=-1)
                ans.push_back(str.substr(mini, maxi-mini+1));
            }
        }

        return ans;
    }
};
85475