Readme

3458.Select-K-Disjoint-Special-Substrings

此题是若干个套路题的缝合。

首先我们要找出所有self-contained的substring，这等同于3104. Find Longest Self-Contained Substring. 例如，我们寻找以字母'a'开头的self-contained的substring，必然会找原字符串中'a'第一次出现的位置start。然后从那个位置往后推进，至少要推进到原字符串中'a'最后一次出现的位置end。在推进的过程中，如果遇到任何新的字符比如说'b'，那么做两件事：

1. 检查'b'第一次出现的位置是否在start之前，如果是的话，那么立即停止并退出。因为包含'a'的自包含的substring无法满足'b'的自包含。
2. 如果通过了第一条，那么我们查看'b'最后一次出现的位置，需要将end更新至更远，以保证'a''b'都是自包含的。

如果推进的过程持续至指针追上了end，那么意味着[start,end]区间内的所有字母都是自包含的。

我们需要判断是否至少有k个区间是彼此不相交的。这就等同于435.Non-overlapping-Intervals. 一个常见的贪心的做法，就是将所有区间按照尾端点排序。贪心的原则就是：如果有若干个彼此相交的区间，根据规则我们最多只能取一个，那必然只会选择尾端点更靠前的，这样会留给后续更多的空间能选择不相交的区间。所以我们必然选择排序后的第一个区间，然后顺序检查后续的区间，如果与其相交的区间都舍弃；此时下一个区间就是选择的第二个区间：因为它与首区间不相交，且尾端点是剩下所有里面最靠前的。以此类推。

事实上，还有更简单的计算逻辑。我们得到的最多26段自包含的区间，要么互斥，要么互相嵌套，不可能出现部分相交的情况。分析见1520. Maximum Number of Non-Overlapping Substrings. 所以我们只需要两两比较，如果大的包含小的，去掉大的即可。