<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) {
        vector<int> left('z' + 1, -1);
        vector<int> right('z' + 1, -1);

        for (int i = 0; i < s.size(); ++i) {
            right[s[i]] = i;
        }
        for (int i = s.size() - 1; i >= 0; --i) {
            left[s[i]] = i;
        }

        vector<int> dpLeft(s.size(), -1);
        vector<pair<int, int>> dp(s.size(), {0, 0});
        vector<pair<int, int>> pred(s.size(), {-1, -1});

        for (char c = 'a'; c <= 'z'; ++c) {
            if (right[c] != -1) {
                int curRight = right[c];
                int curLeft = left[c];
                bool ok = true;
                for (int curPos = curRight; curPos >= curLeft; --curPos) {
                    curLeft = min(curLeft, left[s[curPos]]);
                    if (right[s[curPos]] > curRight) {
                        ok = false;
                        break;
                    }
                }
                if (ok) {
                    dpLeft[curRight] = curLeft;
                }
            }
        }

        for (int i = 0; i < s.size(); ++i) {
            if (i > 0) {
                dp[i] = dp[i - 1];
                pred[i] = pred[i - 1];
            }
            if (dpLeft[i] != -1) {
                int ii = dpLeft[i] - 1;
                int wasCount = 0;
                int wasLength = 0;
                if (ii >= 0) {
                    wasCount = dp[ii].first;
                    wasLength = dp[ii].second;
                }
                int newCount = wasCount + 1;
                int newLength = wasLength + i - ii;
                if (newCount > dp[i].first || (newCount == dp[i].first && newLength < dp[i].second)) {
                    dp[i] = {newCount, newLength};
                    pred[i] = {ii + 1, i};
                }
            }
        }

        vector<string> ans;
        int cur = s.size() - 1;
        while (cur >= 0 && pred[cur].first >= 0) {
            ans.push_back(s.substr(pred[cur].first, pred[cur].second - pred[cur].first + 1));
            cur = pred[cur].first - 1;
        }
        return ans;
    }
};
48175