优化Kotlin最长回文子串代码：移除循环提升速度（Big O）

你的代码现在是枚举所有可能的子串，每个子串还要反转后对比是否是回文，这种方式在字符串较长时会做大量重复工作，自然会超时。

其实可以利用回文中心对称的特性来优化，不用双重循环枚举所有子串——回文要么是奇数长度（中心是单个字符），要么是偶数长度（中心是两个相邻字符之间的位置）。我们只需要遍历每个可能的中心，向两边扩展找到最长的回文即可，外层是单循环，效率会高很多。

下面是实现代码：

class Solution {
    fun longestPalindrome(s: String): String {
        if (s.isEmpty()) return ""
        
        var start = 0
        var end = 0
        
        // 遍历每个位置，作为两种回文的中心
        for (i in s.indices) {
            // 处理奇数长度的回文，中心是s[i]
            val oddLen = expandFromCenter(s, i, i)
            // 处理偶数长度的回文，中心在s[i]和s[i+1]之间
            val evenLen = expandFromCenter(s, i, i + 1)
            
            val currentMaxLen = maxOf(oddLen, evenLen)
            // 如果当前找到的回文比之前的长，更新起止索引
            if (currentMaxLen > end - start) {
                start = i - (currentMaxLen - 1) / 2
                end = i + currentMaxLen / 2
            }
        }
        
        return s.substring(start, end + 1)
    }
    
    // 辅助函数：从指定的左右中心向两边扩展，返回最长回文的长度
    private fun expandFromCenter(s: String, left: Int, right: Int): Int {
        var l = left
        var r = right
        // 只要左右不越界，且字符相等，就继续往外扩
        while (l >= 0 && r < s.length && s[l] == s[r]) {
            l--
            r++
        }
        // 退出循环时，l和r已经不满足条件，所以实际长度是r-l-1
        return r - l - 1
    }
}

简单解释下逻辑： #

• 外层循环只遍历一次字符串的每个字符，对应每个可能的回文中心
• 对每个中心，分别检查奇数长度和偶数长度的回文情况
• 用辅助函数expandFromCenter负责从中心向两边扩散，直到两边字符不相等为止，返回这个中心能扩展出的最长回文长度
• 每次找到更长的回文时，更新记录的起止位置，最后截取对应的子串返回

这种方式避免了大量不必要的子串枚举和反转操作，运行速度会大幅提升，能通过LeetCode的测试用例。

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