Palindrome Problems in Coding Interviews: Expand Around Center, DP and Manacher's Algorithm
2 views
Palindrome questions are a staple of coding interviews because they come in many sizes: an easy two-pointer check, a medium substring search, and harder variants involving partitions or linear-time algorithms. Knowing which technique fits which question saves a lot of time under pressure.
Level 1: checking a palindrome
LeetCode 125 (Valid Palindrome) asks whether a string reads the same backwards after ignoring non-alphanumeric characters and case. Two pointers from both ends, skipping invalid characters, gives O(n) time and O(1) space. The follow-up, LeetCode 680 (Valid Palindrome II), allows deleting one character: when the pointers mismatch, try skipping either the left or the right character and check whether the remainder is a palindrome. Mention that you only branch once, so it stays O(n).
Level 2: longest palindromic substring
LeetCode 5 is the classic. The most practical interview solution is expand around center. Every palindrome has a center, either a single character (odd length) or a gap between two characters (even length). There are 2n - 1 centers, and expanding from each one costs up to O(n), so the total is O(n^2) time and O(1) space.
def longest_palindrome(s):
best = (0, 0)
for c in range(len(s)):
for l, r in ((c, c), (c, c + 1)):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
if r - l - 1 > best[1] - best[0]:
best = (l + 1, r)
return s[best[0]:best[1]]
A DP alternative defines is_pal[i][j] = s[i] == s[j] and is_pal[i+1][j-1]. It is also O(n^2) but uses O(n^2) memory, so explain why you prefer expansion unless you need the table for something else.
Counting palindromic substrings (LeetCode 647) uses the same expansion: add one for every successful step.
Level 3: palindrome partitioning
LeetCode 131 asks for all partitions of a string into palindromes, a backtracking problem where precomputing the is_pal table makes each check O(1). LeetCode 132 asks for the minimum number of cuts: cuts[i] = min(cuts[j - 1] + 1) over all j where s[j..i] is a palindrome. That combines the DP table with a 1D DP, for O(n^2) overall.
Longest palindromic subsequence (LeetCode 516) is different: characters don't need to be contiguous. Use interval DP, where dp[i][j] = dp[i+1][j-1] + 2 if s[i] == s[j], otherwise max(dp[i+1][j], dp[i][j-1]). A neat observation to mention is that this equals the LCS of the string and its reverse.
Level 4: Manacher's algorithm
Manacher finds the longest palindromic substring in O(n). Insert separators (for example "#a#b#a#") so every palindrome has odd length, then maintain the rightmost palindrome boundary and its center. For each new position, its mirror around that center gives a lower bound on its palindrome radius, so you only expand past the known boundary. Each character extends the boundary at most once, which gives linear time.
Most interviewers won't require you to code Manacher, but knowing it exists and explaining the mirror idea in two sentences is a strong signal when they ask, "Can you do better than O(n^2)?"
Interview tips
1. Clarify the input: case sensitivity, character set, empty string.
2. Distinguish substring from subsequence aloud; mixing them up is the most common mistake.
3. Handle both odd and even centers explicitly.
4. State time and space complexity for each approach you mention.
These problems reward a clear explanation as much as correct code. Practicing out loud is the best preparation, and some candidates also use Linkjob AI (https://linkjob.ai) for real-time help during live technical interviews to keep their reasoning structured. Master the center-expansion idea and most palindrome questions become routine.