<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>

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ins insert
#define vii vector<int>
#define pii pair<int,int>
const int N = 1e5+1;
vii graph[26];
vii revGraph[26];
vector<bool>check(26,false);
stack<int>st;
map<int,pii>storeIndex;
int countingArray[N][26];
int n;

void initialize(string& s){
    while(st.size()>0)
        st.pop();

    storeIndex.clear();
    for(int i=0;i<26;i++){
        graph[i].clear();
        revGraph[i].clear();
        check[i] = false;
    }

    for(int i=0;i<n;i++){
        auto itr = storeIndex.find(s[i]-'a');
        if(itr==storeIndex.end())
            storeIndex.ins(mp(s[i]-'a',mp(i,i)));
        else itr->se.se = i;
        for(int j=0;j<26;j++)
            countingArray[i][j] = 0;
    }

    countingArray[0][s[0]-'a'] = 1;
    for(int i=1;i<n;i++){
        for(int j=0;j<26;j++)
            countingArray[i][j] = countingArray[i-1][j];
        countingArray[i][s[i]-'a']++;
    }
}

void dfs1(int u){
    check[u] = true;
    for(auto v: graph[u]){
        if(!check[v])
            dfs1(v);
    }
    st.push(u);
}

void dfs2(int u,vii& temp){
    check[u] = true;
    temp[u] = 1;
    for(auto v: revGraph[u]){
        if(!check[v])
            dfs2(v,temp);
    }
}

class Solution {
public:
    vector<string> maxNumOfSubstrings(string s) {
        n = s.size();
        initialize(s);
        for(int i=0;i<n;i++){
            auto itr = storeIndex.find(s[i]-'a');
            int firstIndex = itr->se.fi;
            int lastIndex = itr->se.se;
            for(int j=0;j<26;j++){
                if(countingArray[lastIndex][j]-countingArray[firstIndex][j]>0){
                    graph[s[i]-'a'].pb(j);
                    revGraph[j].pb(s[i]-'a');
                }
            }
        }

        for(int i=0;i<26;i++){
            auto itr = storeIndex.find(i);
            if(!check[i] && itr!=storeIndex.end())
                dfs1(i);
        }

        for(int i=0;i<26;i++)
            check[i] = false;

        vector<string>finalAns;
        while(st.size()>0){
            int u = st.top();
            st.pop();
            if(!check[u]){
                vii temp(26,0);
                dfs2(u,temp);
                bool noOutDegree = true;
                for(int i=0;i<26;i++){
                    if(temp[i]==1){
                        for(int j=0;j<graph[i].size();j++){
                            if(temp[graph[i][j]]==0)
                                noOutDegree = false;
                        }
                    }
                }
                if(noOutDegree){
                    int minIndex = INT_MAX;
                    int maxIndex = -1;
                    for(int i=0;i<26;i++){
                        if(temp[i]==1){
                            auto itr = storeIndex.find(i);
                            minIndex = min(minIndex,itr->se.fi);
                            maxIndex = max(maxIndex,itr->se.se);
                        }
                    }
                    string temp = "";
                    for(int i=minIndex;i<=maxIndex;i++)
                        temp += s[i];
                    finalAns.pb(temp);
                }
            }
        }
        return finalAns;
    }
};
70555