Longest Palindromic Substring

There are three main approaches. The first expands around every possible centre, treating both odd-length and even-length palindromes, and is quadratic in the worst case. The second uses dynamic programming, building up a table of which substrings are palindromes, and is also quadratic in space. The third is Manacher's algorithm, which reuses information about palindromes already found to keep the total work linear.

The expanding approach is the one to reach for in an interview. Its structure is simple: a palindrome has a centre, which is either a single character for odd lengths or a gap between two characters for even lengths. For each of the n characters and n minus one gaps, expand outwards while the mirrored characters match, and track the longest run found. The total cost is quadratic only when the input is one long palindrome, because each centre then expands all the way to the ends.

The dynamic programming version asks the question differently: is the substring from i to j a palindrome if the characters match and the inner substring from i plus one to j minus one is a palindrome? That recurrence is clean but it fills an n by n table, which is quadratic in memory and usually the wrong trade for a string problem.

The trade-off to name is that Manacher's algorithm is linear but genuinely hard to derive in an interview, and the interviewer cannot expect you to invent it. The honest framing is: I would implement the expanding approach for a single query, and if the string is processed many times or the input is enormous, I would look for a structure that supports repeated queries, such as a palindromic tree, rather than claiming Manacher is obvious.

For every position, try it as the centre of an odd-length palindrome and as the left half of an even-length one. Expand outwards while the characters on both sides match, and keep the longest run found so far.

def longest_palindrome(text):
    best = ""
    for center in range(len(text)):
        for left, right in ((center, center), (center, center + 1)):
            while left >= 0 and right < len(text) and text[left] == text[right]:
                if right - left + 1 > len(best):
                    best = text[left:right + 1]
                left -= 1
                right += 1
    return best

print(longest_palindrome("babad"))
print(longest_palindrome("cbbd"))

The outputs are bab and bb. For babad the longest palindrome has length three, and bab is the first one found; the equally long aba is the mirror of it, so the tie is broken by whichever the scan reaches first. For cbbd the longest is the even-length bb, which is why the even centre case is not optional.

The mechanism is the two-element inner loop. Every palindrome has exactly one centre, either a character or a gap, and the algorithm visits each of them once. For a given centre the expansion is one comparison per level, so the work for that centre is proportional to the palindrome radius at that centre.

The trade-off to name is the worst case. The algorithm is linear on typical text but quadratic on a string of one repeated character, because every centre expands to the boundary. It uses O of 1 extra space, since only the current run is held. The linear-time alternative, Manacher's algorithm, uses a mirrored radius array to avoid re-expanding regions already known, and that is the version to reach for if the string is very long or if you must run the query repeatedly.

The simplest check compares the string with its reverse. Python slicing with a step of minus one produces the reversed string in a single operation, so the whole check is one comparison.

def is_palindrome(text):
    return text == text[::-1]

print(is_palindrome("racecar"))
print(is_palindrome("python"))

The outputs are True and False. A palindrome reads the same forwards and backwards, so racecar is one and python is not.

The cost is linear time and linear space. Building the reversed copy allocates a string of the same length as the input, so for a very long string this doubles the memory needed, and the comparison itself touches every character. The two-pointer version avoids the copy entirely: it walks inwards from both ends comparing characters and returns False at the first mismatch, which uses O of 1 space and, on non-palindromic input, can exit early.

The trade-off to name is that the slicing version is the one-liner you want in a quick script, and it runs faster in practice because the reversal happens in C, whereas the two-pointer version is the one you want when the input is huge, when you cannot afford a copy, or when the interviewer asks for a constant-space solution. It is also worth noting the character-set assumption: the check is only meaningful for single-character comparisons, so a string with combining marks or wide characters needs a more careful comparison than code points.