<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 l[26],r[26];
    int n;
    vector<int> occ[26];
    int mark[26];
    int ad[26][26];
    int adr[26][26];
    int vis[26];
    
    void dfs_mark(int c){
        if(mark[c])return;
        mark[c]=1;
        
        for(int i=0;i<26;i++){
            if(ad[c][i]){
                dfs_mark(i);
            }
        }
    }
    
    void dfs_scc(int c,vector<int> &v){
        if(mark[c])return;
        mark[c]=1;
        v.push_back(c);
        for(int i=0;i<26;i++){
            if(adr[c][i]){
                dfs_scc(i,v);
            }
        }
    }
    
    void dfs_fill(int c,stack<int> &s){
        if(vis[c])return;
        vis[c]=1;
        for(int i=0;i<26;i++){
            if(ad[c][i])dfs_fill(i,s);
        }
        s.push(c);
    }
    
    vector<vector<int> > getSCC(){
        vector<vector<int> > ret;
        for(int i=0;i<26;i++)vis[i]=0;
        stack<int> order;
        
        for(int i=0;i<26;i++){
            if(mark[i]==0&&vis[i]==0){
                dfs_fill(i,order);
            }
        }
        
        for(int i=0;i<26;i++){
            for(int j=0;j<26;j++){
               adr[j][i]=ad[i][j]; 
            }
        }
        
        while(order.size()){
            int i=order.top();
            order.pop();
            if(mark[i]==0){
                //cout<<"deb - found CC\n";
                vector<int> v;
                dfs_scc(i,v);
                ret.push_back(v);
            }
        }
        return ret;
    } 
    
    bool contains(int i,int j)
    {
        int left=0,right=occ[j].size()-1, an=-1;
        while(left<=right){
            int m=(left+right)/2;
            if(occ[j][m]>l[i]){
                an=m;
                right=m-1;
            }
            else left=m+1;
        }
        return occ[j][an]<r[i];
    } 
    
    vector<string> maxNumOfSubstrings(string s) {
        
        for(int i=0;i<26;i++){
            l[i]=-1;
            r[i]=-1;
            mark[i]=0;

            occ[i].clear();
            for(int j=0;j<26;j++)ad[i][j]=0;
        }

        for(int i=0;i<s.size();i++){
            int id=s[i]-'a';
            if(l[id]==-1)l[id]=i;
            r[id]=i;
            occ[id].push_back(i);
        }
        
        for(int i=0;i<26;i++){
            if(l[i]==-1)mark[i]=1;
        }
        
        for(int i=0;i<26;i++){
            for(int j=i+1;j<26;j++){
                if(i==j||r[i]<l[j]||l[i]>r[j])continue;  // no overlap
                if(l[i]<l[j]&&r[j]<r[i]&&!contains(j,i))ad[j][i]=1; // i contains j => i depends on j => j->i
                else if(l[j]<l[i]&&r[i]<r[j]&&!contains(i,j))ad[i][j]=1; // j contains i => j depends on i => i->j 
                else{  // crossing overlap, both depend on each other => i->j, j->i
                    ad[i][j]=1;
                    ad[j][i]=1;
                }
            }
        }
        
        vector<string> ans;
        
        vector<vector<int> > scc=getSCC();
        
        vector<int> compId(26,0);
        
        for(int i=0;i<scc.size();i++){
            for(auto x:scc[i])compId[x]=i;
        }
        
        vector<int> ind((int)scc.size(),0);
        for(int i=0;i<26;i++){
            for(int j=0;j<26;j++){
                if(ad[i][j]&&compId[i]!=compId[j])ind[compId[j]]++;
            }
        }
        
        for(int i=0;i<(int)scc.size();i++){
            if(ind[i]==0){
                int left=INT_MAX,right=INT_MIN;
                for(auto y:scc[i]){
                    left=min(left,l[y]);
                    right=max(right,r[y]);
                }
          
                ans.push_back(s.substr(left,right-left+1));
            }
        }
        
        
        return ans;
    }
};
44445