5. Longest Palindromic Substring

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"

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {\
    // palindromic str for single round
    var o = ""; 
    // Longest palindromic str
    var max = "";
    for (var i = 0; i < s.length; i ++){
        var x = i;
        var y = i;
        // Include current char
            o = s[i];
            
            // Collect Same letters on the right
        while(s[y+1] == s[y]){
            y ++; i ++;
            // append same char on the right to p_str
            o += s[i];
        } 
        
        // Then check both sides one by one
        // Make sure x & y in range, then compare both ends
        while(x > 0 
                && y < s.length-1 
                && s[x-1] == s[y+1]){
            o = s[x-1] + o + s[y+1];
            // Separate x & y for one more step
            x--; y++;
        }
        
        // Save, if longer than current max record
        if(o.length > max.length){
            max = o;
        }
        
    }
    
    return max;
};

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.