Meta 最长回文子串：奇偶中心扩展与Tie规则

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练大小写敏感、返回连续substring，多个同长度结果取最早起点；空串返回空。字符串不能在中间跳过字符。

解题路线

1. 每个字符是奇数回文中心，相邻间隙是偶数回文中心。对每中心同时向左右扩展，只要字符相同就得到更长合法连续回文。
2. 任意非空回文都有唯一中心（字符或间隙），因此所有中心被枚举后不会漏掉最优。每次更新最好(start,length)，并列用start最小固定输出，不随遍历偶然决定。
3. 返回用一次切片，不在每个扩展步复制候选字符串，否则额外引入substring复制成本。索引是码点位置，Unicode组合字符如需按视觉字符比较需先规范化/切分。
4. 如果追问线性算法，Manacher记录每中心半径与最右回文覆盖区，利用镜像半径初值只扩展超过已有边界的部分；应证明全局右边界只向前而非仅报O(n)。本示例保留易核对的中心扩展基线。

手动走一遍

babad有bab与aba长度3，最早起点规则返回bab。cbbd必须检查偶中心得到bb；aaaa扩展中很多重叠候选，但最终长度4；abc返回a。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def longest_palindrome(text):
    """Case sensitive, earliest start breaks equal-length ties."""
    best_start=0;best_len=0
    for center in range(len(text)):
        for left,right in ((center,center),(center,center+1)):
            while left>=0 and right<len(text) and text[left]==text[right]:
                length=right-left+1
                if length>best_len or length==best_len and left<best_start:
                    best_start=left;best_len=length
                left-=1;right+=1
    return text[best_start:best_start+best_len]

复杂度

2n−1有效中心，每中心最坏O(n)扩展，总O(n²)时间、O(1)辅助空间；返回切片O(L)输出空间。Manacher可O(n)时间/O(n)半径空间，不能把中心扩展宣称线性。

易错点与追问

容易失分的边界

• 只检查单字符中心漏掉所有偶数长度回文。
• 最长回文子序列bbbb不能作为bbbab的连续答案。

继续深挖

• 在线逐字符追加时如何更新最长回文？回文树可维护不同回文节点，但复杂度与实现合同需另讲。
• 若并列取字典序最小，要把字符串比较开销计入复杂度。