<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:
    vector<string> maxNumOfSubstrings(string s) {
        int n = s.size();

        // There are 26 characters
        // Create vectors to store first and last occurrence of each character
        vector<int> first(26, n); // Initialize with n (out-of-bound for valid index)
        vector<int> last(26, -1); // Initialize with -1 (out-of-bound for valid index)
        
        for (int i = 0; i < n; i++) {
            int c = s[i] - 'a';
            first[c] = min(first[c], i);
            last[c] = max(last[c], i);
        }

        // Extract all the substrings
        vector<string> storesbs; // Vector to store all the substrings
        for (int i = 0; i < 26; i++) {
            if (first[i] != n) { // Ensure the character exists in the string
                int length = last[i] - first[i] + 1;
                // Ensure length is valid
                if (length > 0 && first[i] + length <= n) {
                    string sbs = s.substr(first[i], length);
                    storesbs.push_back(sbs);
                }
            }
        }

        // Create an adjacency list graph
        vector<vector<int>> adjlist(26); // Initialize adjacency list with 26 empty vectors
        for (auto& substrings : storesbs) { // Iterate through each substring
            int el = substrings[0] - 'a';
            vector<bool> seen(26, false); // Track unique characters in the substring
            for (int i = 1; i < substrings.size(); i++) {
                int c = substrings[i] - 'a';
                if (!seen[c]) {
                    if (el != c) { // Ensure no self-dependency is added
                        adjlist[el].push_back(c);
                    }
                    seen[c] = true; // Mark character as seen
                }
            }
        }

        //Toposort
        stack<int> st;
        vector<int> vis(26,0);
        for(int i =0; i<26; i++)
        {
            if(!vis[i]){dfs(i, st, vis, adjlist);}
        }

        //Transpose
        int n2 = adjlist.size(); // Number of nodes
        vector<vector<int>> transpose(n2); // Initialize transpose graph with empty vectors
        
        for (int i = 0; i < n2; ++i) {
            for (int to : adjlist[i]) {
                transpose[to].push_back(i); // Reverse the edge direction
            }
        }
        
        //New DFS
        vector<int> scc(26, -1); // Stores the SCC ID for each node
        int currentSccId = 0;    // ID for the current SCC being processed

        vector<int> vis2(26,0); //new visited vector
        while(!st.empty())
        {
            int node = st.top(); //node with last finishing time
            st.pop();
            if (!vis2[node]) {
                newDFS(node, transpose, vis2, scc, currentSccId); // Perform DFS on this node
                currentSccId++; // Increment SCC ID after processing an SCC
            }
        }

        vector<int> outdegree(currentSccId, 0); // Vector to track out-degrees of SCCs
        for (int i = 0; i < 26; ++i) {
            for (int neighbor : adjlist[i]) { // Use the original adjacency list
                if (scc[i] != scc[neighbor]) { // If nodes are in different SCCs
                    outdegree[scc[i]]++; // Increment out-degree of the SCC containing `i`
                }
            }
        }

        vector<string> result;
        for (int i = 0; i < currentSccId; ++i) {
            int minIndex = INT_MAX, maxIndex = -1;
            for (int j = 0; j < 26; ++j) {
                if (scc[j] == i) { // Nodes belonging to the same SCC
                    minIndex = min(minIndex, first[j]);
                    maxIndex = max(maxIndex, last[j]);
                }
            }
            if (outdegree[i] == 0) { // SCC with zero out-degree
                string substring = s.substr(minIndex, maxIndex - minIndex + 1);
                if (!substring.empty()) {
                    result.push_back(substring); // Add to result if not empty
                }
            }
        }
            
        return result;
    }


    void newDFS(int node,vector<vector<int>>&transpose, vector<int>& vis2, vector<int>& scc, int currentSccID)
    {
        vis2[node] = 1;
        scc[node] = currentSccID;
        for (int neighbor : transpose[node]) {
            if (!vis2[neighbor]) {
                newDFS(neighbor, transpose, vis2, scc, currentSccID);
            }
        }
    }

    void dfs(int node, stack<int> & st, vector<int>& vis, vector<vector<int>>&adjlist)
    {
        vis[node] = 1;
        for(auto& it: adjlist[node])
        {
            if(!vis[it]) dfs(it, st, vis, adjlist);
        }
        st.push(node);
    }

};
51905