今天來到一題 Medium 的經典題：Longest Palindromic Substring。
題目要求從一個字串中找到最長的「回文子字串」。

題目範例

Input: "babad"
Output: "bab"
解釋："aba" 也可以。

Input: "cbbd"
Output: "bb"

解題方向

回文的定義就是「正著讀、反著讀都一樣」。
最直覺的想法是檢查所有子字串，但這樣時間複雜度 O(n²) * 檢查 O(n)，整體 O(n³)，太慢了。

比較好的方法有兩種：

中心擴展法 (Expand Around Center)

把每個字元（或字元之間的縫隙）當成中心，往兩邊擴展。

每次更新最長的回文子字串。

複雜度 O(n²)，但比暴力法快很多。

DP（動態規劃）

用 DP 表記錄 s[i..j] 是否為回文。

不過實作上比較複雜。

我選擇用 中心擴展法，寫起來比較直觀。

Java 程式碼
class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";

    int start = 0, end = 0;

    for (int i = 0; i < s.length(); i++) {
        int len1 = expandFromCenter(s, i, i);     // 單字元為中心
        int len2 = expandFromCenter(s, i, i + 1); // 兩字元為中心
        int len = Math.max(len1, len2);
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }

    return s.substring(start, end + 1);
}

private int expandFromCenter(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    return right - left - 1;
}

}

小心得

這題一開始會覺得「是不是要窮舉所有子字串？」，但中心擴展法其實很優雅，程式碼也蠻簡單的。
跑起來雖然還是 O(n²)，但在字串長度 ≤ 1000 的情況下，效能完全 OK。

寫完這題之後，對回文問題就更熟悉了。之後如果遇到「子字串」相關的題目，第一直覺就是要考慮 中心擴展 or DP。