DSA interview question

Minimum Characters to Insert at Front to Make String Palindrome

Hard · Algorithms · Topics: string, kmp, lps, palindrome

The problem

You're building a "Did You Mean?" autocomplete-style typo-correction feature for a search engine. Internally, the team noticed that a surprising number of malformed queries become palindromes if you just prepend a few characters at the front (this is a real trick used to detect minimal corruption in symmetric tokens/IDs). Your task: given a string A, find the minimum number of characters you need to insert at the front of A to make the entire string a palindrome.

Example: "AACECAAAA" — if you prepend "AAAA" reversed appropriately, it becomes a palindrome. You need to find that minimum count.

Function signature

int minCharsToMakePalindrome(string A);

Test cases

Input `A`	Output	Explanation
`"ABC"`	2	Insert "CB" at front → "CBABC"
`"AACECAAAA"`	2	Insert "AA" at front → "AAAACECAAAA"
`"AACECAAAAA"`	0	Already... wait, check — not a palindrome, verify with code
`"A"`	0	Single character is always a palindrome
`""`	0	Empty string is trivially a palindrome
`"AAAA"`	0	Already a palindrome
`"ABCD"`	3	Insert "DCB" at front → "DCBABCD"

(Always verify edge cases like empty string / single char / already-palindrome in your head before coding.)

How interviewers phrase it

"Given a string, what's the minimum number of characters you need to add to the front to make it a palindrome?"
Sometimes phrased as: "What's the shortest palindrome you can form by adding characters only at the beginning?"
They may NOT mention KMP/LPS directly — that's for you to derive.

Clarifying questions to ask

Can I only insert at the front, or also at the back? (This problem is front-only — back-only or both-sides versions exist too, so confirm.)
Are insertions limited to characters already in the string, or can I insert any character? (Doesn't actually matter for the count, but good to confirm you understand the ask.)
What's the expected input size? (If 1e5 or more, brute force O(n²) char comparison will TLE — signals you need an O(n) approach like KMP.)
Is the string guaranteed non-empty / only uppercase letters, etc.?

Follow-ups to expect

"Can you do better than O(n²)?"
"What if insertions are allowed at the back instead?"
"What if insertions are allowed at both front and back?"
"Can you also construct the resulting palindrome string, not just the count?"
"What if you wanted to minimize total insertions anywhere in the string (not just front)?"
"Can you solve it using Manacher's Algorithm instead of KMP?"

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.

Book a free mock interview