string - 搜索满足某些条件的最小字符串

Question

最近，我在面试时被问到以下问题。

给定一个字符串 S，我需要找到另一个字符串 S2，使得 S2 是 S 的子序列，并且 S 也是 S2+reverse(S2) 的子序列。这里的“+”表示连接。我需要为给定的 S 输出 S2 的最小可能长度。

有人告诉我这是一个动态规划问题，但我无法解决它。有人可以帮我解决这个问题吗？

编辑-

有没有办法在 O(N2) 或更少的时间内做到这一点。

Answer 1

这个问题有两个重要方面。

由于我们需要 S 作为 S2+reverse(S2) 的子串，S2 应该有
至少 n/2 长度。

在 S2 和 reverse(S2) 串联后，有一个模式，其中
字母重复，如

所以解决方案是检查从 S 的中心到 S 的末尾是否有任何连续的元素。如果您找到一个，请检查任一侧的元素，如图所示。



现在，如果您能够到达字符串的末尾，那么最小元素数(结果)是从起点到您找到连续元素的点的距离。在这个例子中，它的 C 即 3。

我们知道这可能不会总是发生。即您可能无法在中心找到连续的元素。假设连续的元素在中心之后，那么我们可以做同样的测试。

主弦



子串



连接字符串



现在到了主要的疑问。为什么我们只考虑从中心开始的左侧？答案很简单，串联的字符串是由 S+reverse(S) 组成的。所以我们确定子字符串中的最后一个元素在连接的字符串中是连续的。主字符串前半部分的任何重复都无法给出更好的结果，因为至少我们应该在最终连接的字符串中有 n 个字母

现在是复杂的问题:
搜索连续字母给出最大 O(n)
现在迭代地检查任一侧的元素可以给出 O(n) 的最坏情况复杂度。即最多 n/2 次比较。
我们可能会在第二次检查中失败很多次，所以我们在复杂性之间有一个乘法关系，即 O(n*n)。

我相信这是一个正确的解决方案，还没有发现任何漏洞。