Problem

Given a string s, return the longest palindromic substring in s.

Example

  1. Input: s = "babad"
  2. Output: "bab"
  3. Note: "aba" is also a valid answer.
Input: s = "cbbd"
Output: "bb"

Input: s = "a"
Output: "a"

Constraints

  • 1 <= s.length <= 1000.
  • s consist of only digits and English letters.

Solution

我习惯将简单的事情复杂化，解决这个问题的时候，总想着怎么才能将时间复杂度降低到O(N)，导致花费了大量的时间。题目并没有要求时间复杂度和空间复杂度，所以只要使用简单的循环，求出最长回文子字符串即可。

var getLowHigh = (s, i, j) => {
    while (i >= 0 && j < s.length && s[i] === s[j]) {
        i--;
        j++;
    }
    return {low: i + 1, high: j};
}

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
    if (s.length < 2) {
        return s;
    }

    var low = 0;
    var high = 1;

    for (let i = 0; i < s.length; i++) {
        const lh1 = getLowHigh(s, i, i);
        const lh2 = getLowHigh(s, i, i + 1);
        if (lh1.high - lh1.low > high - low) {
            high = lh1.high;
            low = lh1.low;
        }
        if (lh2.high - lh2.low > high - low) {
            high = lh2.high;
            low = lh2.low;
        }
    }

    return s.slice(low, high);
};