<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:
    void Topological(int node , vector <vector <int>> &adj , vector <bool> &vis , stack <int> &st){
        vis[node] = 1;
        for (int i=0 ; i<adj[node].size() ; i++){
            if (!vis[adj[node][i]]) Topological(adj[node][i] , adj , vis , st);
        }
        st.push(node);
    }

    void DFS(int node , vector <vector <int>> &revadj , vector <bool> &vis , vector <int> &temp){
        vis[node] = 1;
        temp.push_back(node);
        for (int i=0 ; i<revadj[node].size() ; i++){
            if (!vis[revadj[node][i]]) DFS(revadj[node][i] , revadj , vis , temp);
        }
    }

    vector<string> maxNumOfSubstrings(string s){
        int n = s.size();
        vector <int> l(26 , n) , r(26 , -1);  // first and last ocurrence of a character
        for (int i=0 ; i<n ; i++){
            if (l[s[i]-'a'] == n){
                l[s[i]-'a'] = i;
            }
            r[s[i] - 'a'] = i;
        }

        vector <vector <int>> adj(26);
        // making adjacency list
        for (int i=0 ; i<26 ; i++){
            if (l[i] != n){
                for (int j = l[i] ; j<=r[i] ; j++){
                    if (s[j] - 'a' != i){
                        adj[i].push_back(s[j]-'a');
                    }
                }
            }
        }

        // Finding topological order
        stack <int> st;
        vector <bool> vis(26 , 0);
        for (int i=0 ; i<26 ; i++){
            if (!vis[i]){
                Topological(i , adj ,vis ,st);
            }
        }

        // // Reverse adj list    
        vector <vector <int>> revadj(26);
        for (int i=0 ;i<26 ; i++){
            for (int j=0 ; j<adj[i].size() ; j++){
                int u = i;
                int v = adj[i][j];
                revadj[v].push_back(u);
            }
        }

        // finding strongly connected component
        vector <vector <int>> sccc;
        for (int i=0 ; i<26 ; i++) vis[i] = 0;

        while (!st.empty()){
            int node = st.top();
            st.pop();
            if (!vis[node]){
                vector <int> temp;
                DFS(node , revadj , vis , temp);
                sccc.push_back(temp);
            }
        }

        vector <int> sccindex(26 , -1); // each node is part of which scc in vector sccs
        for (int i=0 ; i<sccc.size() ; i++){
            for (int j=0 ; j<sccc[i].size() ; j++){
                sccindex[sccc[i][j]] = i;
            }
        }

        // making outdegree array for sccc
        vector <int> outdegree(sccc.size(), 0);
        for (int i=0 ; i<26; i++){
            for (int j=0 ; j<adj[i].size(); j++){
                if (sccindex[i] != sccindex[adj[i][j]]){
                    outdegree[sccindex[i]]++;
                }
            }
        }

        vector <string> result;
        for (int i=0 ; i<sccc.size() ; i++){
            if (outdegree[i] == 0){
                int left = n ; 
                int right = -1;
                for (int j=0 ; j<sccc[i].size() ; j++){
                    left = min(left , l[sccc[i][j]]);
                    right = max(right , r[sccc[i][j]]);
                }
                string temp = s.substr(left , right - left + 1);
                if (!temp.empty()) result.push_back(temp);
            }
        }

        return result;


    }
};
115315