<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 dfs(vector<int> adjT[],int batchID,vector<int> &batch,vector<int> &degree,int v, vector<bool> &visited) {
        if(batch[v] < 0) {
            batch[v] = batchID;
            visited[v] = true;
           for (auto x: adjT[v]) dfs(adjT, batchID, batch, degree, x, visited);

        }
        else if(batch[v] != batchID){
            degree[batch[v]]++;
        }
    }
    void setDfs(stack<int> &st, vector<bool> &visited, vector<int> adj[], int vertex) {
        visited[vertex] = true;

        for (auto x: adj[vertex]) {
            if(visited[x] == false) setDfs(st, visited, adj, x);
        }

        st.push(vertex);
    }
    vector<string> maxNumOfSubstrings(string s) {
        vector<int> minRange(26,INT_MAX), maxRange(26, INT_MIN), exist(26, 0);
        vector<vector<int>> presum(26, vector<int> (s.size()+1, 0));
        for(int i = 0; i < s.size(); i++) {
            minRange[s[i]-'a'] = min(minRange[s[i]-'a'], i);
            maxRange[s[i]-'a'] = max(maxRange[s[i]-'a'], i);
            presum[s[i]-'a'][i+1]++;
            exist[s[i]-'a']++;
            
        }

        for(int i = 0; i < 26; i++) {
            for (int j = 1; j < s.size()+1; j++)
            presum[i][j]+=presum[i][j-1];
        }
        vector<int> adj[26];

        for (int i = 0; i < 26; i++) {
            if(exist[i] != 0) {
                for(int j = 0; j < 26; j++) {
                    
                    // bool minIn = (minRange[j] < maxRange[i] && minRange[j] > minRange[i]);
                    // bool maxIn = (maxRange[j] < maxRange[i] && maxRange[j] > minRange[i]);

                    int maxR = maxRange[i];
                    int minR = minRange[i];
                    if((presum[j][maxR] - presum[j][minR] > 0) && (exist[j] != 0)) {
                        adj[i].push_back(j);
                        // cout << " i " << i << " -> " << j << " j"<<endl;
                    }
                }
            }
        }


        
        stack<int> st;
        vector<bool> visited(26, false);

        for (int i = 0; i < 26; i++) {
            if(exist[i] != 0 && visited[i] == false) {
                setDfs(st, visited, adj, i);
            }
        }
        
        vector<int> batch(26, -1);
        vector<int> degree(26, 0);
        int batchID = 0;

        vector<int> adjT[26];
        for(int i = 0; i < 26; i++) {
            visited[i] = false;
            if(exist[i] != 0) {
                for (auto x: adj[i]) adjT[x].push_back(i);
            }
        }

        // cout << "Size of stack" << st.size() << endl;
        while(st.size() > 0) {
            int v= st.top();
            st.pop();
            if(exist[v] != 0 && visited[v]==false) {
                // cout << "Call here "<< v << endl;
                dfs(adjT, batchID, batch, degree, v, visited);
                batchID++;
            }
        }
        // for (auto x: degree) cout << x <<" ";
        // cout << endl;
        // for (auto x: batch) cout << x << ' ';
        // cout << endl;
        vector<string> ans;
        for(int i = batchID-1; i >= 0; i--) {
            if(degree[i] == 0) {
                
                        // cout << "here " << i << " - "<<endl;
                int minimum = INT_MAX, maximum = -1;
                for (int j = 0; j < 26; j++) {
                    if(batch[j] == i && exist[j] != 0) {
                        minimum = min(minimum, minRange[j]);
                        maximum = max(maximum, maxRange[j]);
                // cout << minimum  << " " << maximum << endl;
                    }
                }
                if(minimum != INT_MAX && maximum != -1) {
                ans.push_back(s.substr(minimum, maximum - minimum + 1));
                }
            }
        }        

        return ans;
        
    }
};
96665