problem

輸入為一字串，回傳字串中最長的回文 (palindrome)。回文是指前到後、後到前寫法一樣的字串，只有一個字元的字串也算是回文。可以假設輸入字串中只會有一個最長回文字串。

sample input:
string = 'abaxyzzyxf'

sample output:
'xyzzyx'

最基本的解法是找出字串中的所有子字串，檢查它們是否為回文，並持續記錄更新最長的回文。但這樣的作法需要 n^3 時間，因為要先以兩層迴圈來找出所有的子字串，再針對每個字串進行 n 操作檢查是否為回文。

另外一個想法是回文的結構左右對稱，也就從中心點向左和向右會是相同的字元，所以可以迴圈過字串，將每個字元都當作回文的中心，向兩邊檢查。另外，回文可能會有偶數字元 'abba' 或奇數字元 'abcba' 兩種結構，也就是最中心可能有兩個相同的字元或只有單一字元，檢查時也要將這點考慮進去。

具體步驟是：

1. 迴圈過字串，對每個字元做兩種檢查：
2. 以當前字元為中心，檢查左邊和右邊字元，如果相等，則繼續檢查左二和右二字元，以此類推。如果超出字串範圍或左右不相等，則看是否更新目前最長回文。
   舉例來說，字串 'abaxyzzyxf'，
   第二個字元 'b' 的左右字元相等，接下來左邊超出範圍，更新目前最長回文為 'aba'。
3. 接下來以當前字元和下一個字元為中心，如果兩者相等，則一樣向左右方繼續比較，直到超出字串範圍或不相等，並更新記錄。也就是說步驟 2 檢查的是奇數字元的回文，而這個步驟檢查的是偶數字元的回文。
4. 最後回傳最長的回文字串。

n 為輸入字串長度，
time: O(n^2) 迴圈過字串需要 n 時間，對每個字元又進行兩種 n 時間的檢查。
space: O(n) 回文長度最長可以為 n。

下方程式碼中，以 getLongest 分別檢查奇數、偶數字元的回文，函式最後 slice() 傳入 left + 1, right 是因為最終跳出 while 迴圈時，left 會是起始索引減一，right 會是結束索引加一。接下來比較偶數和奇數回文的長度，以及當前最長回文的長度，更新記錄。

function longestPalindromicSubstring(string) {
  let currentLongest = '';
  for (let i = 0; i < string.length; i++) {
    const odd = getLongest(string, i - 1, i + 1);
    const even = getLongest(string, i, i + 1);
    const longest = odd.length > even.length ? odd : even;
    currentLongest = currentLongest.length > longest.length ? currentLongest : longest;
  }
  return currentLongest;
}

function getLongest(string, left, right) {
  while (left >= 0 && right < string.length) {
    if (string[left] !== string[right]) break;
    left--;
    right++;
  }
  return string.slice(left + 1, right);
}