查找字符串中最长的非回文子串
Find the longest non-palindromic substring in a string
我需要在一个字符串中找出最长的非回文子串（一个本身不是回文的字符串，不管它的任何子串是否是回文），时间复杂度为 O(n**2)或更少的时间。
我可以想出简单的暴力算法，找到所有可能的子串 (O(n ** 2))，然后对于每个这样的子串检查它是否是回文 (O(n))，取总体复杂度为 O(n**3)。
找出最长回文子串和序列的变体有O(n**2)种，但我无法在这里重用它们来找出解决方案。
如何在 O(n**2) 时间内完成？
设 s,e 为字符串中的位置。
您可以通过检查 string[s] == string[e] 和子串 s+1, e-1 是否也是回文来判断子串 s,e 是否是回文（特殊情况下单个字符 s==e 和空字符串s>e 为真）。
所以最简单的实现是如上所述制作一个递归函数并记住结果（将它们存储在外部矩阵中）。
如果您对迭代小心谨慎，也可以迭代进行（这样您只需要先前计算的结果）。
两者都将填充 O(N^2) 并且单独的计算是微不足道的。
既然已经发布了答案，让我把我的提示变成一个实际的答案：
首先，检查完整字符串是否为：
- 回文（O(n)，平均情况为 O(1)）
- 相同字符的重复，例如"aaaaaaaaaaaa"（在同一个循环中完成）。
然后：
- 如果字符串不是回文，则最长的非回文子串就是字符串本身
- 如果字符串是回文但不是相同字符的重复，则删除任一端将使其成为非回文，并且最长的此类子字符串
- 如果字符串是相同字符的重复，则它没有非回文子串。或者，根据您对回文的定义，唯一的非回文子串是空子串。
我需要在一个字符串中找出最长的非回文子串（一个本身不是回文的字符串，不管它的任何子串是否是回文），时间复杂度为 O(n**2)或更少的时间。
我可以想出简单的暴力算法，找到所有可能的子串 (O(n ** 2))，然后对于每个这样的子串检查它是否是回文 (O(n))，取总体复杂度为 O(n**3)。
找出最长回文子串和序列的变体有O(n**2)种，但我无法在这里重用它们来找出解决方案。
如何在 O(n**2) 时间内完成？
设 s,e 为字符串中的位置。
您可以通过检查 string[s] == string[e] 和子串 s+1, e-1 是否也是回文来判断子串 s,e 是否是回文（特殊情况下单个字符 s==e 和空字符串s>e 为真）。
所以最简单的实现是如上所述制作一个递归函数并记住结果（将它们存储在外部矩阵中）。
如果您对迭代小心谨慎，也可以迭代进行（这样您只需要先前计算的结果）。
两者都将填充 O(N^2) 并且单独的计算是微不足道的。
既然已经发布了答案，让我把我的提示变成一个实际的答案：
首先，检查完整字符串是否为：
- 回文（O(n)，平均情况为 O(1)）
- 相同字符的重复，例如"aaaaaaaaaaaa"（在同一个循环中完成）。
然后：
- 如果字符串不是回文，则最长的非回文子串就是字符串本身
- 如果字符串是回文但不是相同字符的重复，则删除任一端将使其成为非回文，并且最长的此类子字符串
- 如果字符串是相同字符的重复，则它没有非回文子串。或者，根据您对回文的定义，唯一的非回文子串是空子串。