The single rule in this problem is deceptively powerful: if a substring contains any occurrence of a character `c`, it must contain *all* of them. That constraint means a valid substring is never something I freely carve out — it's a closure. Once I decide where a block starts, the block is forced to swallow every occurrence of every character it touches, and I keep widening until nothing new is pulled in. ### Building the candidate blocks For each letter I first record `first[c]` and `last[c]` in a single sweep. Then, for a letter `c`, I start with the span `[first[c], last[c]]` and scan it left to right, pushing the right edge out whenever some character inside reaches past the current end. Two things can happen: - I meet a character whose *first* occurrence sits to the left of my start. Then the block can only be closed by also moving the left edge outward, so this letter can never begin a legal substring — I throw the candidate away. - The scan finishes cleanly. Now `[lo, hi]` is the smallest legal block that starts at `first[c]`. That gives me at most one candidate interval per distinct character — 26 of them at most, regardless of how long `s` is. ### Why greedy scheduling wins Every legal substring is one of these closed candidates: its leftmost character generates exactly that block. So I never have to look beyond the handful of candidates I built. Picking the maximum number of non-overlapping ones is the classic activity-selection problem — sort by right endpoint, then take an interval whenever its left endpoint clears the last one I kept. That greedy choice is provably count-optimal. The minimum-total-length requirement comes along for free. The closed candidates are non-crossing: any two are either disjoint or nested. Because of that, the earliest-finishing interval the greedy picks at each step is also the shortest available, and no selection with the same count can be shorter. ### Worked example `s = "adefaddaccc"`. The block generated by `a` spans the first `a` to the last `a` and, closing over `d`, becomes `"adefadda"`. The block for `e` is just `"e"`, for `f` just `"f"`, and for `c` it's `"ccc"`. Sorted by right endpoint and taken greedily, `"e"`, `"f"`, and `"ccc"` are mutually disjoint and give 3 — the `a`-block overlaps `e`/`f`, so keeping the three short ones beats keeping the long one. That matches the expected `["e","f","ccc"]`. ### Complexity - Time `O(n)`: one scan to fill `first`/`last`, then `O(26 · n)` worst case to close the candidates — linear in `n`. Sorting 26 intervals is constant. - Space `O(1)` beyond the output: two size-26 arrays and at most 26 intervals. ### Code (C++) ```cpp class Solution { public: vector maxNumOfSubstrings(string s) { int n = s.size(); vector first(26, -1), last(26, -1); for (int i = 0; i < n; ++i) { int c = s[i] - 'a'; if (first[c] < 0) first[c] = i; last[c] = i; } // For each character present, compute the minimal valid interval that // starts at first[c] and is closed under "contains all occurrences of // every character it covers". If expansion ever needs to go left of the // start, this character cannot begin a valid substring -> skip it. vector> intervals; // (right, left) for (int c = 0; c < 26; ++c) { if (first[c] < 0) continue; int lo = first[c], hi = last[c]; bool ok = true; for (int i = lo; i <= hi; ++i) { int d = s[i] - 'a'; if (first[d] < lo) { ok = false; break; } if (last[d] > hi) hi = last[d]; } if (ok) intervals.push_back({hi, lo}); } // Interval scheduling: sort by right endpoint, greedily take // non-overlapping ones. Maximizes count; each interval is already the // minimal closure for its start, so total length is minimized too. sort(intervals.begin(), intervals.end()); vector ans; int prevRight = -1; for (auto& [r, l] : intervals) { if (l > prevRight) { ans.push_back(s.substr(l, r - l + 1)); prevRight = r; } } return ans; } }; ```