<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 helper(map<int, vector<int>>& adj, vector<int>& vis, int node, stack<int>& st)
    {
        vis[node] = 1;
        for(auto i: adj[node])
        {
            if(vis[i])
                continue;
            
            helper(adj, vis, i, st);
        } 
        st.push(node);
    }

    void revDFS(map<int, vector<int>>& transpose, vector<int>& vis, int node, vector<int>& temp)
    {
        vis[node] = 1;

        if(transpose[node].size() == 0)
            return;

        temp.push_back(node);
        for(auto i: transpose[node])
        {
            if(vis[i])
                continue;

            revDFS(transpose, vis, i, temp);
        }
    }

    void checkDFS(map<int, vector<int>>& adj, vector<int>& v, int node, map<int, int>& mp, int& flag)
    {
        v[node] = 1;

        for(auto i: adj[node])
        {
            if(mp[i] != 1)
            {
                flag = 0;
                return;
            }

            if(!v[i])
            {
                checkDFS(adj, v, i, mp, flag);
            }
        }
    }

    vector<string> maxNumOfSubstrings(string s) {
        int n = s.size();
        vector<int> leftoccur(26, INT_MAX), rightoccur(26, INT_MIN);

        for(int i=0; i<n; i++)
        {
            leftoccur[s[i] - 'a'] = min(leftoccur[s[i] - 'a'], i);
            rightoccur[s[i] - 'a'] = i;
        }

        map<int, vector<int>> adj;

        for(int i=0; i<n; i++)
        {
            for(int j=0; j<26; j++)
            {
                if(leftoccur[s[i] - 'a'] != INT_MAX)
                {
                    if((leftoccur[j] <= i) && (i <= rightoccur[j]))
                    {
                        adj[j].push_back(s[i] - 'a');
                    }
                }
            }
        }

        // Kosaraju 
        // Step 1- Topology Sort

        n = 26;
        vector<int> vis(n, 0);
        stack<int> st; 
        for(int i=0; i<n; i++)
        {
            if(!vis[i])
                helper(adj, vis, i, st);
        }

        // Step 2- Transpose the graph
        map<int, vector<int>> transpose;
        for(int i=0; i<26; i++)
        {
            vis[i] = 0;
            for(auto j: adj[i])
            {
                transpose[j].push_back(i);
            }
        }

        // Step 3- Reverse DFS
        vector<vector<int>> res;
        while(!st.empty())
        {
            int top = st.top();
            st.pop();

            if(vis[top])
                continue;

            vector<int> temp;
            revDFS(transpose, vis, top, temp);
            res.push_back(temp);
        }

        vector<string> ans;
        for(auto i: res)
        {
            vector<int> v(n, 0);

            if(i.size())
            {
                map<int, int> mp;

                for(auto j: i)
                    mp[j] = 1;

                int flag = 1;
                checkDFS(adj, v, i[0], mp, flag);
                if(flag)
                {
                    int mini = 1e9;
                    int maxi = -1;
                    for(auto j: i)
                    {
                        mini = min(mini, leftoccur[j]);
                        maxi = max(maxi, rightoccur[j]);
                    }
                    ans.push_back(s.substr(mini, maxi-mini+1));
                }
            }
        }
        return ans;
    }
};
148885