<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:
    vector<string> maxNumOfSubstrings(string S)
    {
         int mins[26], maxs[26], prefixSum[26] = {0}, degree[26] = {0}, batches[26];
        bool exists[26] = {false};
        bool graph[26][26];
        // Initialize arrays for tracking min and max indices and existence of each character
        for (int i = 0; i < 26; i++)
        {
            mins[i] = INT_MAX;
            maxs[i] = -1;
            batches[i] = -1;
            exists[i] = false;
            degree[i] = 0;
            prefixSum[i] = 0;
            for (int j = 0; j < 26; j++)
            {
                graph[i][j] = false;
            }
        }

        // Step 1: Precompute min and max indices and prefix sums
        for (int i = 0; i < S.length(); i++)
        {
            int index = S[i] - 'a';
            mins[index] = min(mins[index], i);
            maxs[index] = max(maxs[index], i);
            exists[index] = true;
        }

        vector<vector<int>> prefixSumTable(S.length() + 1, vector<int>(26, 0));
        for (int i = 0; i < S.length(); i++)
        {
            for (int j = 0; j < 26; j++)
            {
                prefixSumTable[i + 1][j] = prefixSumTable[i][j];
            }
            prefixSumTable[i + 1][S[i] - 'a'] += 1;
        }

        // Step 2: Build the graph using adjacency matrix
        for (int i = 0; i < 26; i++)
        {
            if (exists[i])
            {
                for (int j = 0; j < 26; j++)
                {
                    if (prefixSumTable[maxs[i] + 1][j] - prefixSumTable[mins[i]][j] > 0)
                    {
                        graph[i][j] = true;
                    }
                }
            }
        }

        // Step 3: Apply Kosaraju's algorithm to find SCCs
        stack<int> stack;
        vector<bool> visited(26, false);

        for (int i = 0; i < 26; i++)
        {
            if (exists[i] && !visited[i])
            {
                dfs(i, graph, stack, visited);
            }
        }

        int batch = 0;
        while (!stack.empty())
        {
            int v = stack.top();
            stack.pop();
            if (batches[v] < 0)
            {
                dfs(v, graph, batches, batch, degree);
                batch++;
            }
        }

        // Step 4: Find SCCs with zero out-degree and construct the result
        vector<string> res;
        for (int i = batch - 1; i >= 0; i--)
        {
            if (degree[i] == 0)
            {
                int minIndex = INT_MAX, maxIndex = -1;
                for (int j = 0; j < 26; j++)
                {
                    if (batches[j] == i)
                    {
                        minIndex = min(mins[j], minIndex);
                        maxIndex = max(maxs[j], maxIndex);
                    }
                }
                res.push_back(S.substr(minIndex, maxIndex - minIndex + 1));
            }
        }

        return res;
    }

private:
    void dfs(int v, bool graph[26][26], stack<int> &stack, vector<bool> &visited)
    {
        if (!visited[v])
        {
            visited[v] = true;
            for (int i = 0; i < 26; i++)
            {
                if (graph[v][i] && !visited[i])
                {
                    dfs(i, graph, stack, visited);
                }
            }
            stack.push(v);
        }
    }

    void dfs(int v, bool graph[26][26], int batches[26], int batch, int degree[26])
    {
        if (batches[v] < 0)
        {
            batches[v] = batch;
            for (int i = 0; i < 26; i++)
            {
                if (graph[i][v])
                {
                    dfs(i, graph, batches, batch, degree);
                }
            }
        }
        else
        {
            if (batches[v] != batch)
            {
                degree[batches[v]]++;
            }
        }
    }
};

178725