Explanation: Notice that while the set of substrings ["d","abba","cc"] also has length 3, it's considered incorrect since it has larger total length.

Constraints

1 <= s.length <= 10^5
s contains only lowercase English letters.

Solution

Method 1 – Greedy + Interval Merging

Intuition

For each character, find the leftmost and rightmost occurrence. For each character, expand its interval to include all characters inside it. Then, greedily select the smallest non-overlapping intervals.

Approach

For each character, record its first and last occurrence in the string.
For each character, expand its interval to cover all characters inside its current interval.
Collect all such intervals and sort them by their end index.
Greedily select non-overlapping intervals with the smallest end index.
Return the selected substrings.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    vector<string> maxNumOfSubstrings(string s) {\n        int n = s.size();\n        vector<int> l(26, n), r(26, -1);\n        for (int i = 0; i < n; ++i) {\n            l[s[i]-'a'] = min(l[s[i]-'a'], i);\n            r[s[i]-'a'] = max(r[s[i]-'a'], i);\n        }\n        vector<pair<int, int>> intervals;\n        for (int c = 0; c < 26; ++c) {\n            if (l[c] > r[c]) continue;\n            int left = l[c], right = r[c], changed = 1;\n            while (changed) {\n                changed = 0;\n                for (int i = left; i <= right; ++i) {\n                    int cc = s[i] - 'a';\n                    if (l[cc] < left) { left = l[cc]; changed = 1; }\n                    if (r[cc] > right) { right = r[cc]; changed = 1; }\n                }\n            }\n            if (left == l[c]) intervals.emplace_back(right, left);\n        }\n        sort(intervals.begin(), intervals.end());\n        vector<string> ans;\n        int last = -1;\n        for (auto& [r, l] : intervals) {\n            if (l > last) {\n                ans.push_back(s.substr(l, r-l+1));\n                last = r;\n            }\n        }\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">    vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">string</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">> </span><span st

Related Tags