string - 查找字符串中最长的非回文子串

Question

我需要在 O(n**2) 或更少的字符串中找出最长的非回文子串(一个本身不是回文的字符串，不管它的任何子串是否是回文)时间。

我可以想出简单的蛮力算法，找到所有可能的子串 (O(n ** 2))，然后为每个这样的子串检查它是否是回文 (O(n))，计算整体复杂度到 O(n**3)。

找出最长回文子串和序列的变体有 O(n**2) 种，但我无法在这里重用它们来找出解决方案。

如何在 O(n**2) 时间内完成？

Answer 1

既然已经发布了一个答案，让我把我的提示变成一个实际的答案:

首先，检查完整的字符串是否是:

• 回文(O(n)，平均情况为 O(1))
• 相同字符的重复，例如“aaaaaaaaaaaa”(在同一循环中完成)。

然后:

• 如果字符串不是回文，则最长的非回文子串就是字符串本身
• 如果字符串是回文但不是相同字符的重复，则删除任一端将使它成为非回文，并且最长的此类子串
• 如果字符串是相同字符的重复，则它没有非回文子串。或者，根据您对回文的定义，唯一的非回文子串是空子串。