Problem: 5. 最長回文子串

整體思路

這段代碼旨在解決經典的 “最長回文子串” (Longest Palindromic Substring) 問題。問題要求在一個給定的字符串 S 中，找到一個最長的、內容左右對稱的連續子串。

該算法采用了一種非常高效且簡潔的 中心擴展 (Expand From Center) 算法。其核心思想是，任何一個回文串，都有一個中心。這個中心可能是一個字符（對于奇數長度的回文串，如 “aba” 的中心是 ‘b’），也可能是兩個字符之間的空隙（對于偶數長度的回文串，如 “abba” 的中心在兩個 ‘b’ 之間）。

算法的邏輯步驟如下：

1. 統一中心處理：

   • 該算法最巧妙的一點是，它通過一個 for 循環 for (int i = 0; i < 2 * n - 1; i++) 來遍歷所有可能的中心。
   • 一個長度為 n 的字符串，有 n 個單字符中心和 n-1 個字符間的中心，總共 2n-1 個。
   • 通過 l = i / 2 和 r = (i + 1) / 2 這兩個計算，可以巧妙地將這 2n-1 個虛擬中心索引 i 映射到字符串的實際索引起點：
     • 當 i 是偶數時（例如 i=4），l 和 r 會相等（l=2, r=2），這對應一個單字符中心，用于查找奇數長度的回文串。
     • 當 i 是奇數時（例如 i=5），r會比l大1（l=2, r=3），這對應一個字符間中心，用于查找偶數長度的回文串。

2. 從中心向兩邊擴展：

   • 對于每一個確定的中心 (l, r)，算法進入一個 while 循環。
   • 這個循環同時將左指針 l 向左移動 (l--) 和右指針 r 向右移動 (r++)，并持續檢查以下條件：
     a. 指針沒有越界 (l >= 0 && r < n)。
     b. 兩邊指針指向的字符相等 (s[l] == s[r])。
   • 只要這些條件滿足，就說明當前 [l, r] 范圍內的子串是一個回文串，可以繼續嘗試擴展。

3. 更新最長回文串記錄：

   • 當 while 循環因不滿足條件而終止時，最后一個有效的回文串是在 l 和 r 停止移動之前的位置，即 [l+1, r-1]。
   • 該回文串的長度為 (r-1) - (l+1) + 1 = r - l - 1。
   • 算法將這個長度與已記錄的最長回文串的長度進行比較。如果當前找到的更長，就更新 ansLeft 和 ansRight 來記錄這個新發現的最長回文串的邊界。

4. 返回結果：

   • 在遍歷完所有 2n-1 個中心后，ansLeft 和 ansRight 中存儲的就是全局最長回文子串的起始索引（包含）和結束索引（不包含）。
   • 最后，使用 S.substring(ansLeft, ansRight) 截取并返回結果。

完整代碼

class Solution {/*** 找到字符串 S 中的最長回文子串。* @param S 輸入的字符串* @return 最長的回文子串*/public String longestPalindrome(String S) {// 將字符串轉換為字符數組，可以略微提高字符訪問效率。char[] s = S.toCharArray();int n = s.length;// ansLeft: 記錄最長回文子串的起始索引（包含）。int ansLeft = 0;// ansRight: 記錄最長回文子串的結束索引（不包含）。int ansRight = 0;// 核心循環：遍歷所有 2n-1 個可能的中心。// i 是一個虛擬的中心索引。for (int i = 0; i < 2 * n - 1; i++) {// 通過 i 計算出中心擴展的起始左右指針。// 如果 i 是偶數, l=r, 對應單字符中心 (奇數長度回文串)。// 如果 i 是奇數, r=l+1, 對應字符間中心 (偶數長度回文串)。int l = i / 2;int r = (i + 1) / 2;// 從中心 (l, r) 向兩邊擴展，尋找回文串。while (l >= 0 && r < n && s[l] == s[r]) {l--;r++;}// 循環結束后，最后一個有效回文串的邊界是 [l+1, r-1]。// 其長度為 (r-1) - (l+1) + 1 = r - l - 1。// 當前記錄的最長長度為 ansRight - ansLeft。if (r - l - 1 > ansRight - ansLeft) {// 如果找到了更長的回文串，則更新記錄。// 新的起始索引是 l+1。ansLeft = l + 1;// 新的結束索引（不包含）是 r。ansRight = r;}}// 根據記錄的邊界，從原始字符串 S 中截取最長回文子串。return S.substring(ansLeft, ansRight);}
}

時空復雜度

時間復雜度：O(N^2)

1. 外層循環：for (int i = 0; i < 2 * n - 1; i++) 遍歷了 2n-1 次，其復雜度為 O(N)。
2. 內層循環：while (...) 循環是從每個中心向外擴展。在最壞的情況下（例如，字符串本身就是一個大回文串 “aaaaa…”），從中心開始的擴展可能會一直延伸到字符串的兩端。每次擴展的操作數最多是 N/2 次（向左 N/2，向右 N/2）。因此，內層循環的復雜度是 O(N)。
3. 綜合分析：
   總的時間復雜度是外層循環和內層循環復雜度的乘積。即 O(N) * O(N) = O(N^2)。

空間復雜度：O(1)

1. 主要存儲開銷：算法的核心邏輯只使用了固定數量的整型變量（n, ansLeft, ansRight, i, l, r）來存儲指針和結果邊界。
2. toCharArray()：char[] s = S.toCharArray(); 創建了字符串的一個副本，占用了 O(N) 的空間。然而，在標準的算法復雜度分析中，這種對輸入的表示轉換通常不被計入額外輔助空間（auxiliary space），因為核心算法本身（指針操作）并不需要這部分空間（可以直接使用 S.charAt()）。
3. 綜合分析：
   如果我們只考慮算法邏輯本身所需的額外空間，那么空間復雜度為 O(1)。