<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 {
    static constexpr int ALPHABET_SIZE = 26;

    void dfs(const vector<int>& graph, vector<bool>& visited, stack<int>& nodeStack, int node) {
        visited[node] = true;
        for (int nbr = 0; nbr < ALPHABET_SIZE; nbr++) {
            if ((graph[node] & (1 << nbr)) && !visited[nbr]) {
                dfs(graph, visited, nodeStack, nbr);
            }
        }
        nodeStack.push(node);
    }

    void reverseDfs(const vector<int>& graph, vector<int>& batches, vector<int>& batchOutDegree, int node, int batch) {
        batches[node] = batch;
        for (int nbr = 0; nbr < ALPHABET_SIZE; nbr++) {
            if (graph[nbr] & (1 << node)) {
                if (batches[nbr] == -1) {
                    reverseDfs(graph, batches, batchOutDegree, nbr, batch);
                } else if (batches[nbr] != batch) {
                    batchOutDegree[batches[nbr]]++;
                }
            }
        }
    }

    pair<int, pair<vector<int>, vector<int>>> kosarajuSCC(const vector<int>& graph, int exists) {
        stack<int> nodeStack;
        vector<bool> visited(ALPHABET_SIZE, false);
        for (int i = 0; i < ALPHABET_SIZE; i++) {
            if ((exists & (1 << i)) && !visited[i]) {
                dfs(graph, visited, nodeStack, i);
            }
        }

        vector<int> batches(ALPHABET_SIZE, -1);
        vector<int> batchOutDegree(ALPHABET_SIZE, 0);
        int currBatch = 0;

        while (!nodeStack.empty()) {
            int currNode = nodeStack.top();
            nodeStack.pop();
            if (batches[currNode] == -1) {
                reverseDfs(graph, batches, batchOutDegree, currNode, currBatch);
                currBatch++;
            }
        }

        return {currBatch, {batches, batchOutDegree}};
    }

public:
    vector<string> maxNumOfSubstrings(string s) {
        int first[ALPHABET_SIZE];
        int last[ALPHABET_SIZE];
        int exists = 0;
        vector<vector<int>> prefix(s.size() + 1, vector<int>(ALPHABET_SIZE, 0));
        vector<int> graph(ALPHABET_SIZE, 0);

        fill(begin(first), end(first), INT_MAX);
        fill(begin(last), end(last), -1);

        for (int i = 0; i < s.size(); i++) {
            prefix[i + 1] = prefix[i];
            prefix[i + 1][s[i] - 'a']++;
            first[s[i] - 'a'] = min(first[s[i] - 'a'], i);
            last[s[i] - 'a'] = max(last[s[i] - 'a'], i);
            exists |= (1 << (s[i] - 'a'));
        }

        for (int i = 0; i < ALPHABET_SIZE; i++) {
            if (exists & (1 << i)) {
                for (int j = 0; j < ALPHABET_SIZE; j++) {
                    if (prefix[last[i] + 1][j] > prefix[first[i]][j]) {
                        graph[i] |= (1 << j);
                    }
                }
            }
        }

        vector<string> resultArr;
        auto sccData = kosarajuSCC(graph, exists);
        int currBatch = sccData.first;
        const auto& batches = sccData.second.first;
        const auto& batchOutDegree = sccData.second.second;

        for (int i = currBatch - 1; i >= 0; i--) {
            if (batchOutDegree[i] == 0) {
                int minval = INT_MAX, maxval = INT_MIN;
                for (int j = 0; j < ALPHABET_SIZE; j++) {
                    if (batches[j] == i) {
                        minval = min(minval, first[j]);
                        maxval = max(maxval, last[j]);
                    }
                }
                resultArr.push_back(s.substr(minval, maxval - minval + 1));
            }
        }

        return resultArr;
    }
};

171265