删除第一个、第二个、最后一个或倒数第二个字符 K 次后的最小词典字符串

Question

题：

给定一个字符串 SS.length() <= 5.10^5和一个整数 K K <= S.length()。对于每次移除，您可以：

• 删除字符串的第一个字符
• 删除字符串的第二个字符
• 删除字符串的最后一个字符
• 删除字符串的倒数第二个字符

我怎样才能准确地进行 K 次删除，以使最终字符串具有最小的字典顺序？

例子：

S = "abacaaba", K = 2

• 删除字符串的第二个字符
• 删除字符串的倒数第二个字符

最后一个字符串：“aacaaa”，这是可能的最小字典。

附：

我已经尝试了很多天，但无法找到解决此问题的有效方法。但我认为这与动态规划有关。

Answer 1

这是一个（希望）大部分完整的 Python 解决方案（抱歉，我对 C++ 更不熟悉）。我相信这个想法与 David Eisenstat 的相同或非常相似，他的回答帮助我更多地思考如何处理中间部分。中间部分的比较使用 O(1) 查找和 O(n log n) 预处理，基于代码中引用和链接的后缀数组构造（David 的建议是使用 O(n) 预处理和 O(1) 查找，但是我还没有时间了解 O(1) RMQ 或 Ukkonen 的；我也对引用的 CP 后缀数组算法着迷）。该代码包括与暴力比较的测试，但不完整，因为它不处理只有前缀和后缀而没有中间的情况，无论如何处理应该更简单。可能有一些方法可以使代码更加简洁和有组织，但我还没有时间更仔细地考虑它。

因为我们可以删除第一个、第二个、倒数第二个或最后一个字符；解决方案的前两个字母将从 k 或更少删除后剩余的两个字母（子序列）中选择：

xxxAxxxxxxxB...

一旦我们通过删除一些第一个字符来确定角色 A，我们就只能根据我们对第二个字符的删除次数来选择 B。显然，我们想要 A 的最低可用字符，我们可能有多个实例，然后是 B 的最低选择，我们也可能有多个实例。

后缀的组成类似，但我们需要为每个已为前缀选择的 k - num_deletions 存储最佳后缀。那么最终的候选是最低的两个字符前缀+中间+两个字符后缀，其中中间由每个候选中删除的分布固定。我们可以使用后缀数组或树与附加信息来比较中间值。

Python

xxxAxxxxxxxB...