不知道做完 Easy版本的Valid Palindrome看到這一題 Medium版Longest Palindromic Substring 的你有什麼想法？

一開始我看到這題的想法是：
我先把所有的Substring找出來，然後確認它是不是Palindrome後，存起來，並且用個空間紀錄目前最長的答案。

於是我就來暴力Coding一下

function longestPalindromicSubstring(string) {
  let longest = '';
  for (let i = 0; i < string.length; i++) {
    for (let j = i; j < string.length; j++) {
      const substring = string.slice(i, j + 1);
      if (substring.length > longest.length && isPalindrome(substring)) {
        longest = substring;
      }
    }
  }
  return longest;
}

function isPalindrome(string) {
  let start = 0;
  let end = string.length - 1;
  while (start < end) {
    if (string[start] !== string[end]) return false;
    start++;
    end--;
  }
  return true;
}

不過，這個方法會花到Ｏ(n^3)，算是很糟糕的方式。
因為要找出Substring這件事我們就需要使用兩次迴圈，此外，所有的Substring都要去呼叫確認是否為palindrome的方法->isPalindrome(string)，也就是我們昨天實作出來的結果，它的時間複雜度是Ｏ(N)。

來想想有沒有更好的做法。
先來觀察一下Palindrome
'我愛你愛我'，假設今天這是在地板上的5個格子中的字，我們跳到第三格格子，發現往左右兩邊看都是"愛我"。
那如果今天是'我愛你你愛我'，我們一跳到第三格跟第四格中間的線上，發現往左右兩邊看都是"你愛我"。
有沒有一點感覺了？
如果我們是一個裁判，我們只要在一個點上去計算我們左右兩邊看過去會是相同的長度，就可以知道這個Palindrome的長度是多少。可以分成：
在奇數長度時中心點會恰好是一個字

ab|c|ba
<-   ->

在偶數長度時中心會在線上

ab|ba
<- ->

利用這種方式，時間複雜度可以降到Ｏ(n^2)，因為我們每次都確認當下的字和前一個字的左右擴展，而每個擴展最多都花Ｏ(n)，而空間Ｏ(1)。

語法補充：

slice() 方法會回傳一個新陣列物件，為原陣列選擇之 begin 至 end（不含 end）部分的淺拷貝（shallow copy）。而原本的陣列將不會被修改。

參考: Array.prototype.slice()

最後把想法換成程式碼吧！

var longestPalindrome = function (s) {
  let currentLongest = [0, 1];
  for (let i = 1; i < s.length; i++) {
    const odd = getLongestPalindrome(s, i - 1, i + 1);
    const even = getLongestPalindrome(s, i - 1, i);
    const longest = odd[1] - odd[0] > even[1] - even[0] ? odd : even;
    currentLongest = currentLongest[1] - currentLongest[0] > longest[1] - longest[0] ? currentLongest : longest;
  }
  return s.slice(currentLongest[0], currentLongest[1]);
};

function getLongestPalindrome(string, leftIndex, rightIndex) {
  while (leftIndex >= 0 && rightIndex < string.length) {
    if (string[leftIndex] != string[rightIndex]) break;
    rightIndex++;
    leftIndex--;
  }
  return [leftIndex + 1, rightIndex];
}

明日題目預告：
Subsets