LC 1520. 最多的不重叠子字符串

https://leetcode-cn.com/problems/maximum-number-of-non-overlapping-substrings/

这题出现在了 lc weekly contest 198 上，这题是第3题属于medium难度，第4题属于hard难度，但是第4题反而做出来的人比较多。我也属于这多数人中的一个。直观感觉是这题没有什么套路，另外其实这个问题有两个子问题需要解决，所以我觉得还是蛮难的。

第一个子问题就是区间扩展。假设 "babab" 这样的字符串，我们要计算“如果要覆盖a字符的话，那么最小区间什么？”这样的问题。

最开始包含字符a的区间是 [1,3]
但是[1,3]中间存在b字符，而b字符的区间是[0,4], 所以区间扩展到了[0,4]
如此往复直到区间不在变化

这样看上去算法似乎蛮简单的，但是当时就真的不知道如何处理，主要还是没有遇到过类似问题。

这个操作的时间复杂度如何呢？其实还是有保证的。因为我们每次遍历至少会纳入1个字符，因为只有26个字符所以最多遍历26遍。所以处理一个字符的时间复杂度是 O(26*n). 如果处理所有字符的话，那么复杂度就是 O(26 * 26 * n).

第二个子问题是，如果我们拿到了“覆盖x字符的最小区间”之后，我们如何选取“区间数量最多，区间总长度最短”的最优区间覆盖呢？这个子问题让我想起了课程安排问题。课程安排问题可以使用贪心算法解决，这个问题也可以，只不过贪心选择的指标不同。至于这题，贪心选择指标是：

假设区间表示为 (end, length), end 表示结束为止，length 表示长度
我们首先选择 end 最小的，如果 end 相同的话（这是有可能的，因为第一步扩展之后两个字符的区间可能完全相同，比如 "ababa"这样的情况），那么选择长度length最小的。
实现上我们对 (end, length) 排序，然后顺序处理，确保两个区间不会重合。

为什么我们这么选择呢？证明贪心一般使用反证法。[x1, y1] 和 [x2, y2]. 假设y1<y2，并且我们首先选择[x2,y2]，如果可以将[x2,y2]替换成为[x1,y1]的话，看上去情况并不会变的更糟糕。同理可以证明长度选择的顺序。

class Solution:
    def maxNumOfSubstrings(self, s: str) -> List[str]:
        ss = [ord(x) - ord('a') for x in s]
        rs = [[-1, -1] for _ in range(26)]
        n = len(ss)
        for i in range(n):
            c = ss[i]
            if rs[c][0] == -1:
                rs[c][0] = i
            rs[c][1] = i

        ext = rs.copy()
        for c in range(26):
            p0, p1 = rs[c]
            if p0 == -1:
                continue

            changed = True
            while changed:
                changed = False
                cs = set(ss[p0:p1 + 1])
                p2, p3 = p0, p1
                for i in range(26):
                    if i not in cs: continue
                    p2 = min(p2, rs[i][0])
                    p3 = max(p3, rs[i][1])
                if p2 != p0 or p3 != p1:
                    changed = True
                p0, p1 = p2, p3
            ext[c] = [p0, p1]

        ext = [(x, y) for x, y in ext if x != -1]
        ext.sort(key=lambda x: (x[1], -x[0]))
        st = []
        for x, y in ext:
            if st and st[-1][1] >= x:
                continue
            st.append((x, y))

        ans = []
        for x, y in st:
            ans.append(s[x:y + 1])
        ans.sort(key=lambda x: (len(x), x))
        return ans