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

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

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

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

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

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

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

为什么我们这么选择呢?证明贪心一般使用反证法。[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