<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:
    int graph[26][26];
    int vis[26] = {0};
    int exists[26] = {0};
    int col[26] = {0};
    vector <int> topo;
    void dfs(int a){
        vis[a] = 1;
        for(int i = 0; i < 26; i++) if(!vis[i] && graph[a][i]) dfs(i);
        topo.push_back(a);
    }
    void dfs2(int a, int cnt){
        col[a] = cnt;
        for(int i = 0; i < 26; i++) if(!col[i] && graph[i][a]) dfs2(i, cnt);
    }
    vector<string> maxNumOfSubstrings(string s) {
        map <int, int> mx, mn; 
        for(int i = 0; i < s.size(); i++){
            exists[s[i]-'a'] = 1;
            if(!mn.count(s[i]-'a')) mn[s[i]-'a'] = i;
        }
        for(int i = s.size() - 1; i >= 0; i--){
            if(!mx.count(s[i]-'a')) mx[s[i]-'a'] = i;
        }
        int dp[s.size()][26];
        for(int i = 0; i < 26; i++) dp[0][i] = 0;
        dp[0][s[0]-'a'] = 1;
        for(int i = 1; i < s.size(); i++){
            for(int j = 0; j < 26; j++) dp[i][j] = dp[i-1][j];
            dp[i][s[i]-'a']++;
        }
        for(int i = 0; i < 26; i++) for(int j = 0; j < 26; j++) graph[i][j] = 0;
        for(int i = 0; i < 26; i++){
            for(int j = 0; j < 26; j++){
                if(!exists[i] || !exists[j]) continue;
                if(dp[mx[i]][j] - dp[mn[i]][j] > 0) graph[i][j] = 1;
            }
        }
        topo.clear();
        for(int i = 0; i < 26; i++){
            if(!vis[i] && exists[i]) dfs(i);
        }
        reverse(topo.begin(), topo.end());
        int cnt = 1;
        for(auto i: topo){
            if(!col[i] && exists[i]) {
                dfs2(i, cnt);
                cnt++;
            }
        }
        vector <pair <int, pair <int, int>>> res;
        for(int i = 1; i < cnt; i++){
            int mnv = 1e9, mxv = -1e9;
            for(int j = 0; j < 26; j++){
                if(col[j] != i) continue;
                mnv = min(mnv, mn[j]);
                mxv = max(mxv, mx[j]);
            }
            res.push_back({mxv - mnv + 1, {mnv, mxv}});
        }
        sort(res.begin(), res.end());
        set <int> st;
        vector <pair<int, int>> fin;
        for(auto i: res){
            if(st.lower_bound(i.second.first) == st.lower_bound(i.second.second)){
                st.insert(i.second.first);
                st.insert(i.second.second);   
                fin.push_back(i.second);
            }
        }
        vector <string> ans;
        for(auto i: fin){
            string temp;
            for(int j = i.first; j <= i.second; j++) temp+=s[j];
            ans.push_back(temp);
        }
        return ans;
    }
};
40715