K次删除首尾或次首尾字符后求最小字典序字符串

给定长度为n的字符串S（n <= 5*10^5）和整数K（K <= n），每次删除操作可以移除当前字符串的首字符、第二个字符、尾字符、倒数第二个字符，要求恰好执行K次删除，求能得到的字典序最小的最终字符串。

由于每次只能删除当前串的前两个或后两个位置的字符，永远无法删除中间位置的字符，因此所有合法的最终字符串仅能属于以下四类：

1. 两端无额外保留字符：最终串是S的一段长度为m = n-K的连续子串
2. 仅保留左端首个字符：最终串结构为S[0] + 一段长度为m-1的连续子串
3. 仅保留右端末尾字符：最终串结构为一段长度为m-1的连续子串 + S[n-1]
4. 同时保留两端字符：最终串结构为S[0] + 一段长度为m-2的连续子串 + S[n-1]
   我们只需要分别求出四类中的最小字典序串，再取四者的最小值即可，该结论可通过样例验证：
   样例输入S="abacaaba"，K=2，m=6，类型4的候选串为S[0] + S[2..5] + S[7] = "a"+"acaa"+"a" = "aacaaa"，恰好是样例输出的最优解。

1. 提前处理边界情况：K=0直接返回原串，K=n直接返回空串
2. 预处理字符串的前缀哈希和幂数组，支持O(log n)时间比较任意两个子串的字典序大小；如果追求最优复杂度，可使用DC3算法构造后缀数组，实现O(1)子串比较
3. 求类型1的最小串：遍历所有长度为m的连续子串，找到字典序最小的
4. 求类型2的最小串（仅当m >= 1时有效）：遍历所有符合要求的长度为m-1的连续子串，找到最小的后前面拼接S[0]
5. 求类型3的最小串（仅当m >= 1时有效）：遍历所有符合要求的长度为m-1的连续子串，找到最小的后后面拼接S[n-1]
6. 求类型4的最小串（仅当m >= 2时有效）：遍历所有符合要求的长度为m-2的连续子串，找到最小的后前后拼接S[0]和S[n-1]
7. 比较所有有效候选串，输出最小的那个

使用哈希+二分比较的方案总复杂度为O(n log n)，使用后缀数组的方案总复杂度为O(n)，两种方案都可以轻松处理5*10^5的数据规模。

内容的提问来源于stack exchange，提问作者unglinh279