Longest Palindromic Substring - Coding Interview Question

Recently did a video on determining if strings are palindromes. There's another LeetCode question that expands on this a bit by wanting us to return the longest palindromic substring instead.

We're given a string, say "420RACECAR1337". We want to return "RACECAR", because that's the longest palindrome found inside the string.

Looking at this string, you can see that it's a palindrome by scanning each character and then checking the characters on each side and see if they are the same. For instance, if you're looking at the E in the above string, you can look to the left and right of that character and see that they are the same. You can keep expanding until you find different characters.

So, let's code it.

We can start with an empty string and looping through the input. We can expand around the center to try to find a palindrome for each character index in the string. If it's longer than the current string, we just update it.

function longestPalindrome(string: string): string {
    let result = '';

    for (let index = 0; index < string.length; index++) {
        const expanded = expand(string, index);
        if (expanded.length > result.length) result = expanded;
    }

    return result;
};

We need an expand function to check surrounding characters and return the substring it found. It will start with left and right pointers, starting at the index. Then it loops until characters found at the left and right index are not equal or it hits the end of the string.

function expand(string: string, index: number): string {
    let left = index;
    let right = index;

    while (left >= 0 && right < string.length && string[left] === string[right]) {
        left -= 1;
        right += 1;
    }

    return string.substring(left + 1, right);
}

There's an issue with this logic though. If we have an even string like "ABBA", it won't work because there's no center character with surrounding equal characters. We can fix it by making an offset parameter such that for palindromes that need to expand around two letters it doesn't break the loop.

function expand(string: string, index: number, offset: boolean): string {
    let left = index;
    let right = index + (offset ? 1 : 0);

    while (left >= 0 && right < string.length && string[left] === string[right]) {
        left -= 1;
        right += 1;
    }

    return string.substring(left + 1, right);
}

And then of course we just have to handle this case in our main loop with the offset flag set to false and true respectively.

function longestPalindrome(string: string): string {
    let result = '';

    for (let index = 0; index < string.length; index++) {
        const expanded = expand(string, index, false);
        const expandedEven = expand(string, index, true);
        if (expanded.length > result.length) result = expanded;
        if (expandedEven.length > result.length) result = expandedEven;
    }

    return result;
};

And there you have it. Now you have a function that can handle both odd or even palindromes.