# 5.Longest Palindromic Substring <span class='tag' data-diff='medium'></span>
{%hackmd RN5D4nggQRO8wzNqxuvlNw %}

## 題目
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
**Example 1:**

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

**Example 2:**

Input: "cbbd"
Output: "bb"

## 思路
這一題的解法本來想用dynamic programming，但想不出要怎麼bottom up的更新表格，所以改用別的方法。建立一個表格，計算從每個字元開始，可以長出最大的回文字串。
首先，先loop過整個字串初始化這個表格，初始化的方法先看該字元的前後兩個是否相同，若是，則紀錄以該字元為中心的最常回文字串長度為3。不過，需要考慮到中心為數個重複字元的情況，在該種情況下，在初始化時，會數此字元附近有多少個相同字元，並將總數紀錄到正中間的字元上。

let c = s.split('').map(x => 1);
s.split("").map((x,i) => {
    if(s[i+1] == s[i-1]  && s[i+1] != s[i]) c[i] = 3;
    else {
        let j = i + 1;
        while(j < s.length){
            if(s[i] != s[j]) break;
            c[Math.floor((j-i) / 2) + i] = Math.max(c[Math.floor((j-i)/2) + i], j - i + 1);
            j ++;
        }
    }
});

接下來，loop過這個表格，略過在第一階段沒有超過1的字元，開始往其左右找能不能在加長。另外建立一個tuple，記錄目前最大長度與該回文字串的中心，計算完每個字元後，如果以其為中心的最長回文字串超過目前的最大長度，則更新這個tuple。

let max = [0,0];
c.map((x,i) => {
    let left = 0, right = 0;

    if(x < 2) return;
    else if(x % 2){ 
        // odd
        while(1){
            left = i - (c[i] + 1) / 2,
            right = i + (c[i] + 1) / 2;
            if(left < 0 || right >= s.length || s[left] != s[right]) break;
            c[i] += 2;
        }
    }
    else {
        //even
        while(1){
            left = i - c[i] / 2,
            right = i + c[i] / 2 + 1;
            if(left < 0 || right >= s.length || s[left] != s[right]) break;
            c[i] += 2;
        }
    }
    if(c[i] > max[0]){
        max[0] = c[i];
        max[1] = i;
    }
});  

最後在回傳答案的時候，還需要考慮兩個特殊狀況，沒有超過1個字長度以上的回文字串與空字串，前者的情況只要max這個tuple最大長度為0，回傳第一個字即可，而空字串的情況是前一個的特例，這時取第一個字`s[0]`會得到`undefine`，所以這時再與空字串本身做或運算，則可得到空字串的結果。

if(max[0] == 0) return s[0] || s;
return s.substring(max[1] - Math.floor((max[0]-1) / 2), max[1] + Math.ceil((max[0]+1) / 2))

這個解法差不多會花費$O(n^2)$的時間複雜度，因為每個字元都可能往兩側擴張$n/2$的距離。而空間複雜度則是我們的技術表格，所需花費為$O(n)$。雖然在LeetCode上速度只贏過5、60%的人，但已經心滿意足了www
另外，看了解析中的DP解，發現也是要$O(n^2)$的時間複雜度，而且DP解的空間複雜度也是$O(n^2)$，看來好像沒有用DP解比較厲害(?)