讀完本文，你可以去力扣拿下如下題目：
5.最長迴文子串
-----------
迴文串是面試常常遇到的問題（雖然問題本身沒啥意義），本文就告訴你迴文串問題的核心思想是什麼。
首先，明確一下什：迴文串就是正著讀和反著讀都一樣的字串。
比如說字串 aba 和 abba 都是迴文串，因為它們對稱，反過來還是和本身一樣。反之，字串 abac 就不是迴文串。
可以看到迴文串的的長度可能是奇數，也可能是偶數，這就添加了迴文串問題的難度，解決該類問題的核心是雙指標。下面就透過一道最長迴文子串的問題來具體理解一下回文串問題：
string longestPalindrome(string s) {}對於這個問題，我們首先應該思考的是，給一個字串 s，如何在 s 中找到一個迴文子串？
有一個很有趣的思路：既然迴文串是一個正著反著讀都一樣的字串，那麼如果我們把 s 反轉，稱為 s'，然後在 s 和 s' 中尋找最長公共子串，這樣應該就能找到最長迴文子串。
比如說字串 abacd，反過來是 dcaba，它的最長公共子串是 aba，也就是最長迴文子串。
但是這個思路是錯誤的，比如說字串 aacxycaa，反轉之後是 aacyxcaa，最長公共子串是 aac，但是最長迴文子串應該是 aa。
雖然這個思路不正確，但是這種把問題轉化為其他形式的思考方式是非常值得提倡的。
下面，就來說一下正確的思路，如何使用雙指標。
尋找回文串的問題核心思想是：從中間開始向兩邊擴散來判斷迴文串。對於最長迴文子串，就是這個意思：
for 0 <= i < len(s): 找到以 s[i] 為中心的迴文串 更新答案但是呢，我們剛才也說了，迴文串的長度可能是奇數也可能是偶數，如果是 abba這種情況，沒有一箇中心字元，上面的演算法就沒轍了。所以我們可以修改一下：
for 0 <= i < len(s): 找到以 s[i] 為中心的迴文串 找到以 s[i] 和 s[i+1] 為中心的迴文串 更新答案PS：讀者可能發現這裡的索引會越界，等會會處理。
二、程式碼實現按照上面的思路，先要實現一個函式來尋找最長迴文串，這個函式是有點技巧的：
string palindrome(string& s, int l, int r) { // 防止索引越界 while (l >= 0 && r < s.size() && s[l] == s[r]) { // 向兩邊展開 l--; r++; } // 返回以 s[l] 和 s[r] 為中心的最長迴文串 return s.substr(l + 1, r - l - 1);}為什麼要傳入兩個指標 l 和 r 呢？因為這樣實現可以同時處理迴文串長度為奇數和偶數的情況：
for 0 <= i < len(s): # 找到以 s[i] 為中心的迴文串 palindrome(s, i, i) # 找到以 s[i] 和 s[i+1] 為中心的迴文串 palindrome(s, i, i + 1) 更新答案下面看下 longestPalindrome 的完整程式碼：
string longestPalindrome(string s) { string res; for (int i = 0; i < s.size(); i++) { // 以 s[i] 為中心的最長迴文子串 string s1 = palindrome(s, i, i); // 以 s[i] 和 s[i+1] 為中心的最長迴文子串 string s2 = palindrome(s, i, i + 1); // res = longest(res, s1, s2) res = res.size() > s1.size() ? res : s1; res = res.size() > s2.size() ? res : s2; } return res;}至此，這道最長迴文子串的問題就解決了，時間複雜度 O(N^2)，空間複雜度 O(1)。
樣，但是空間複雜度至少要 O(N^2) 來儲存 DP table。這道題是少有的動態規劃非最優解法的問題。
另外，這個問題還有一個巧妙的解法，時間複雜度只需要 O(N)，不過該解法比較複雜，我個人認為沒必要掌握。該演算法的名字叫 Manacher's Algorithm（馬拉車演算法），有興趣的讀者可以自行搜尋一下。