5. Longest Palindromic Substring

Problem

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Solution

One

http://articles.leetcode.com/longest-palindromic-substring-part-ii
Non-trivial O(N) solution. Interesting to read but no use for preparing an interview.

Two

O(N^2) at worst case. Find each center point and expand it.

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

    var len = 1, start = 0
    for (let i = 1; i < s.length; i += 1) {
        if (s[i] === s[i-1]) {
            let j = i-2
            let k = i+1
            while(j >= 0 && k < s.length && s[j] === s[k]) {
                j -= 1
                k += 1
            }
            if (k - j - 1 > len) {
                len = k - j - 1
                start = j + 1
            }
        }

        if (s[i-1] === s[i+1]) {
            let j = i-2
            let k = i+2
            while(j >= 0 && k < s.length && s[j] === s[k]) {
                j -= 1
                k += 1
            }
            if (k - j - 1 > len) {
                len = k - j - 1
                start = j + 1
            }
        }
    }

    return s.substr(start, len)
};