<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(int node, vector<vector<int>> &g, vector<bool> &vis, stack<int> &st){
        vis[node]=1;
        for(auto ne: g[node])
        {
            if(!vis[ne])
                dfs(ne, g, vis, st);
        }
        st.push(node);
    }
    void dfs2(int node, vector<vector<int>> &gr, vector<bool> &vis, vector<int> &v){
        vis[node]=1;
        v.push_back(node);
        for(auto ch: gr[node]){
            if(!vis[ch])
                dfs2(ch, gr, vis, v);
        }
    }
    void dfs_to_check_outdegree(int v, vector<vector<int>> &g, map<int,int> &mp, vector<int> &vis, bool &f){
        vis[v] = 1;
        for(auto ch: g[v]){
            if(mp[ch] != 1) {
                f = false; return;
            }
            if(!vis[ch]){
                dfs_to_check_outdegree(ch, g, mp, vis, f);
            }
        }
    }

    vector<string> maxNumOfSubstrings(string s) {
        //SEE LAST PAGE OF THE NEW COPY THAT I BOUGHT IN PONDI - FOR EXPLANATION !!!!
        int n=s.length();
        //storing the leftmost and rightmost index of each character
        vector<int> left(26,-1), right(26,-1);
        for(int i=0;i<s.length();i++)
        {
            int idx=s[i]-'a';
            if(left[idx]==-1)
            {
                left[idx]=i;
            }
            right[idx]=i;
        }

        vector<vector<int>> g(26), rg(26);
        //sde sheet striver article- why we make reverse graph
        for(int i=0;i<n;i++)
        {
            int ch=s[i]-'a';
            for(int j=0;j<26;j++)
            {
                //checking if i comes b/w j
                if(ch!=j && left[j]!=-1 && ((i>left[j] && i<right[j])))
                {
                    g[j].push_back(ch);
                    rg[ch].push_back(j);
                }
            }
        }

        //printing graph
        // for(int i=0;i<26;i++)
        // {
        //     cout<<i<<": ";
        //     for(auto ch: g[i])
        //     {
        //         cout<<ch<<" ";
        //     }
        //     cout<<endl;
        // }

        vector<bool> vis(26, 0);
        stack<int> scc_st;
        //to get all the nodes in the order of their finish time
        for(int i=0;i<26;i++)
        {
            if(!vis[i] && left[i]!=-1)
            {
                dfs(i, g, vis, scc_st);
            }
        }
        // stack<int> temp=scc_st;
        // while(!temp.empty())
        // {
        //     cout<<temp.top()<<" ";
        //     temp.pop();
        // }
        // cout<<endl;

        vector<vector<int>> scc;
        vis= vector<bool> (26, 0);
        while(!scc_st.empty())
        {
            int node= scc_st.top();
            scc_st.pop();
            if(!vis[node])
            {
                vector<int> v;
                dfs2(node, rg, vis, v);
                scc.push_back(v);
            }
        }

        vector<string> ans;
        // cout<<"printing scc"<<endl;
        for(auto it: scc){
            vector<int> visted(26,0);
            map<int,int> mp;
            for(auto ele: it)
            {
                // cout<<ele<<" ";
                mp[ele]=1;
            }
            // cout<<endl;
            bool flg = true;

            //this is to check if our current scc has any outgoing edge to some other node or not
            dfs_to_check_outdegree(it[0], g, mp, visted, flg);
            if(flg == true){
                int min_l = 1e9, max_r = -1;
                for(auto ele: it){
                    min_l = min(min_l, left[ele]);
                    max_r = max(max_r, right[ele]);
                }
                ans.push_back(s.substr(min_l,max_r-min_l+1));
            }            
        }

        return ans;
    }
};
100395