题目描述

给你一个只包含小写字母的字符串 s，你需要找到 s 中最多数目的非空子字符串，满足如下条件：

• 这些字符串之间互不重叠，也就是说对于任意两个子字符串 s[i..j] 和 s[k..l]，要么 j < k 要么 i > l。
• 如果一个子字符串包含字符 c，那么 s 中所有 c 字符都应该在这个子字符串中。

请你找到满足上述条件的最多子字符串数目。如果有多个解法有相同的子字符串数目，请返回这些子字符串总长度最小的一个解。可以证明最小总长度解是唯一的。

请注意，你可以以 任意 顺序返回最优解的子字符串。

样例

输入：s = "adefaddaccc"
输出：["e","f","ccc"]
解释：下面为所有满足第二个条件的子字符串：
[
  "adefaddaccc"
  "adefadda",
  "ef",
  "e",
  "f",
  "ccc",
]
如果我们选择第一个字符串，那么我们无法再选择其他任何字符串，所以答案为 1。
如果我们选择 "adefadda"，剩下子字符串中我们只可以选择 "ccc"，它是唯一不重叠的子字符串，所以答案为 2。
同时我们可以发现，选择 "ef" 不是最优的，因为它可以被拆分成 2 个子字符串。
所以最优解是选择 ["e","f","ccc"]，答案为 3。不存在别的相同数目子字符串解。

输入：s = "abbaccd"
输出：["d","bb","cc"]
解释：注意到解 ["d","abba","cc"] 答案也为 3，但它不是最优解，因为它的总长度更长。

限制

• 1 <= s.length <= 10^5
• s 只包含小写英文字母。

算法

(贪心) $O(n)$

1. 首先求出每个字母第一次出现的位置 first[c] 和最后一次出现的位置 last[c]。
2. 迭代更新这些区间，即如果当前字母的区间中包含了另外的字母，则用另外的字母的区间来更新当前字母的区间。
3. 现在我们得到了一些区间，目标是求出最多互不重叠的区间，且长度最小。我们可以通过按右区间端点从小到大排序，然后扫一遍就可以得到答案。

时间复杂度

• 迭代更新时，每个字母区间最多需要迭代 26 次，且每个字母区间迭代完成时总共需要扫描 $O(n)$ 次。
• 最多有 26 个区间，排序扫描的时间都是常数。
• 故总时间复杂度为 $O(n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储数据结构。

C++ 代码

class Solution {
    const int m = 26;
    int n;
private:
    void update(const vector<bool> &seen, const string &s,
                vector<int> &newFirst, vector<int> &newLast) {
        vector<int> oldFirst(m, n), oldLast(m, -1);
        vector<unordered_set<int>> dep(m);

        for (int c = 0; c < m; c++) {
            if (!seen[c]) continue;
            for (int i = newFirst[c]; i <= newLast[c]; i++)
                if (c != s[i] - 'a')
                    dep[c].insert(s[i] - 'a');

            oldFirst[c] = newFirst[c];
            oldLast[c] = newLast[c];
        }

        queue<int> q;
        for (int c = 0; c < m; c++)
            if (seen[c])
                q.push(c);

        while (!q.empty()) {
            int c = q.front();
            q.pop();

            for (int d : dep[c]) {
                newFirst[c] = min(newFirst[c], oldFirst[d]);
                newLast[c] = max(newLast[c], oldLast[d]);
            }

            for (int i = newFirst[c]; i < oldFirst[c]; i++)
                if (c != s[i] - 'a')
                    dep[c].insert(s[i] - 'a');

            for (int i = oldLast[c]; i < newLast[c]; i++)
                if (c != s[i] - 'a')
                    dep[c].insert(s[i] - 'a');

            if (newFirst[c] < oldFirst[c] || newLast[c] > oldLast[c]) {
                oldFirst[c] = newFirst[c];
                oldLast[c] = newLast[c];
                q.push(c);
            }
        }
    }

public:
    vector<string> maxNumOfSubstrings(string s) {
        n = s.size();
        vector<bool> seen(m, false);
        vector<int> first(m, n), last(m, -1);

        for (int i = 0; i < n; i++) {
            int c = s[i] - 'a';
            if (!seen[c]) first[c] = i;
            last[c] = i;
            seen[c] = true;
        }

        update(seen, s, first, last);

        vector<int> p(m);
        for (int c = 0; c < m; c++)
            p[c] = c;

        sort(p.begin(), p.end(), [&](int x, int y) {
            if (last[x] != last[y])
                return last[x] < last[y];

            return last[x] - first[x] < last[y] - first[y];
        });

        int st = 0;
        while (!seen[p[st]]) st++;

        int lastPos = -1;
        vector<string> ans;
        for (; st < m; st++) {
            int c = p[st];
            if (first[c] > lastPos) {
                ans.push_back(s.substr(first[c], last[c] - first[c] + 1));
                lastPos = first[c];
            }
        }

        return ans;
    }
};