Hard · Algorithms · Topics: dynamic programming, string, lps
The problem
You're building a "symmetric ID repair" tool for a legacy inventory system, where product codes are supposed to be palindromic (a validation quirk baked in decades ago), but due to a data-entry bug, some codes came out slightly malformed. Unlike the earlier "insert only at front" problem, this time insertions are allowed anywhere in the string — front, back, or middle. Given a string s, find the minimum number of characters you need to insert (anywhere) to make it a palindrome.
(This is LeetCode 1312 — distinct from the earlier "front-only" LPS/KMP problem. Confirm which variant is being asked.)
How interviewers phrase it
"Given a string, what's the minimum number of characters you need to insert anywhere to make it a palindrome?"
"Find the minimum insertions to make this string a palindrome" (no positional restriction mentioned — that's your cue this is the general DP version, not the front-only KMP version).
Sometimes phrased as a lead-in: "You solved Edit Distance and LCS-based problems — now, using similar ideas, how would you make a string a palindrome with minimum insertions?"
Clarifying questions to ask
Can insertions happen anywhere in the string (front, middle, back), or only at one end? (Critical — if only front, it's the KMP/LPS-prefix problem instead; if anywhere, it's this DP problem.)
Is deletion allowed too, or strictly insertions only?
Are we minimizing insertion count, or do we also need the final palindrome string itself?
Case-sensitive matching?
What's the expected string length? (Signals whether O(n²) DP is fine, or if they want the O(n log n) LCS-via-suffix-array style optimization — usually O(n²) is fully acceptable here.)
Follow-ups to expect
"How does this relate to Longest Palindromic Subsequence (LPS)?"
"How does this relate to LCS?"
"Can you reconstruct the actual palindrome, not just the count?"
"Can you optimize space?"
"What if insertions had different costs depending on the character?"
"Compare/contrast with the 'insert only at front' version you solved earlier."
Practise questions like this with a real engineer
On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.