The problem

I need to find the longest substring within any given string that is a palindrome.

Brute Forcing it

The brute force approach is the same as the previous problem's, where we identify all potential substrings, check if they're palindromes and then choose the longest one. This would again have an O(N^3) time complexity.

Finding a proper solution

My initial thought was to go Two Pointer again, starting outward in, since you can check to see if a string is a palindrome by marching your two pointers in lockstep, confirming they have the same value until they converge. I especially liked this idea, because I thought the winning palindrome will be the first I find, since starting at the edges means I'd be evaluating the longest options first. That said, this idea broke down when I realized that there's no clean algorithm for handling failure cases. Do I march the left pointer up and try again? The right pointer down? What if the longest palindrome is the last N chars of the array, but I've marched the right pointer past those values? This plan unfortunately won't work.

What will work, though, is walking forward through the array and viewing each point as the potential center of the palindrome, marching outward from there until the pointers don't match, and then storing the result if it's larger than the largest we've already found. The palindrome might also be of even length, so for each place in the array, I'll also need to check if array[i] == array[i + 1], and if so, treat those two as the center of the palindrome.

Coding the solution

Here's my initial solution -

function longestPalindrome(s: string): string {
    const chars = s.split("")
    let longest = chars[0]
    for (let i = 0; i < chars.length; i++) {
        // odd palindrome
        let left = i - 1;
        let right = i + 1;
        while (!(left < 0 || right > chars.length - 1) && chars[left] === chars[right]) {
            if (s.substring(left, right + 1).length > longest.length) {
                longest = s.substring(left, right + 1);
            }
            left -= 1
            right += 1
        }
        // even palidrome

        if (chars[i] == chars[i + 1]) {
            left = i;
            right = i + 1;
            let currSubstring = s.substring(left, right + 1);
            if (currSubstring.length > longest.length) {
                longest = currSubstring
            }
            while (!(left < 0 || right > chars.length - 1) && chars[left] === chars[right]) {
                let currSubstring = s.substring(left, right + 1);

                if (currSubstring.length > longest.length) {
                    longest = currSubstring
                }
                left = left - 1
                right = right + 1
            }

        }
    }
    return longest
}

This took me a while to finally get right. My first mistake was, I'm so used to my left and right points moving in instead out, I originally had my pointers moving in the wrong direction. I also have a decent amount of duplicate code between the odd and even traversals, so any change I made in one I needed to make in the other.

This solution is technically O(N^2), because every new additional to the array creates a new potential center, and therefore another worst case N operations.

Final thoughts

• Sometimes even when I arrive at the correct logical solution, actually writing the code is still challenging.

• There are definitely further optimizations that can be made to ensure this runs faster. In my solution, every time we move centers, we're looking through indices we've already looked at, and there's likely a more optimal way of only looking at unchecked values once I've found a palindrome, but that's an investigation for another day.