<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<vector<int>>& graph, vector<int>& vis,stack<int>& stk, int node){
        vis[node] = 1;
        for(int i=0;i<graph[node].size();i++){
            if (!vis[graph[node][i]]){
                dfs(graph,vis,stk,graph[node][i]);
            }
        }
        stk.push(node);
    }

    void dfs(vector<vector<int>>& graph, vector<int>& vis,string &s, int node){
        vis[node] = 0;
        s.push_back(node + 'a');
        for(int i=0;i<graph[node].size();i++){
            if (vis[graph[node][i]]){
                dfs(graph,vis,s,graph[node][i]);
            }
        }
    }

    bool check(vector<vector<int>>& graph, vector<int>&vis, map<int,int>& mp, int node){
        vis[node] = 1;
        if (!mp[node]){
            return false;
        }
        bool flag= true;
        for(int i=0;i<graph[node].size();i++){
            if (!vis[graph[node][i]])
                flag &= check(graph,vis,mp,graph[node][i]);
        }
        return flag;
    }

    vector<string> maxNumOfSubstrings(string s) {
        int n = s.size();

        vector<int> left(26,INT_MAX),right(26,INT_MIN);
        for(int i=0;i<n;i++){
            left[s[i]-'a'] = min(i,left[s[i]-'a']);
            right[s[i]-'a'] = max(i, right[s[i]-'a']);            
        }

        vector<vector<int>> graph(26,vector<int>(0)),graphTranspose(26,vector<int>(0));
        for(int i=0;i<n;i++){
            for(int j=0;j<26;j++){
                if(left[j] <= i && right[j] >= i){
                    graph[j].push_back(s[i]-'a');
                    graphTranspose[s[i]-'a'].push_back(j);
                }
            }
        }

        vector<int> vis(26,0);
        stack<int> stk;

        for(int i=0;i<26;i++){
            if (graph[i].size() && !vis[i]){
                dfs(graph,vis,stk,i);
            }
        }

        vector<string> scc;
        while(!stk.empty()){
            int node = stk.top();stk.pop();
            if (vis[node]){
                string s;
                dfs(graphTranspose,vis,s,node);
                if (s.size())
                    scc.push_back(s);
            }
        }

        // for(int i=0;i<26;i++){
        //     cout<<char('a'+i)<<": ";
        //     for(int j=0;j<graph[i].size();j++){
        //         cout<<char('a'+graph[i][j])<<" ";
        //     }
        //     cout<<endl;
        // }

        vector<string> ans;
        for(int i=0;i<scc.size();i++){
            map<int,int> mp;
            for(int j= 0;j<scc[i].size();j++){
                mp[scc[i][j]-'a'] = 1;
            }
            vector<int> vis(26,0);
            if (check(graph,vis,mp,scc[i][0]-'a')){
                int l=left[scc[i][0]-'a'],r=right[scc[i][0]-'a'];
                for(int j=0;j<scc[i].size();j++){
                    l = min(l, left[scc[i][j]-'a']);
                    r = max(r, right[scc[i][j]-'a']);
                }
                ans.push_back(s.substr(l,r-l+1));
            }

        }
        return ans;

    }
};
119045