PPractick

The problem

You're working on a "smart undo" feature for a text editor that auto-completes symmetric brackets/tags. Specifically, given a string s, your job is to find the shortest palindrome you can build by adding characters only at the front of s. Unlike a previous task where you only needed the count of characters to add, here you need to return the actual resulting palindrome string.

Example: s = "aacecaaa" → adding "aa" to the front gives "aaaacecaaa", which is a palindrome — and it's the shortest possible.

Function signature

string shortestPalindrome(string s);

Test cases

Input s	Output	Explanation
"aacecaaa"	"aaacecaaa"	Add "aa" at front (wait — verify with code, see note below)
"abcd"	"dcbabcd"	Add "dcb" at front
""	""	Empty string is already a palindrome
"a"	"a"	Single char is already a palindrome
"aaaa"	"aaaa"	Already a palindrome, nothing to add
"abb"	"bbabb"	Add "bb" at front
"abcde"	"edcbabcde"	Add "edcb" at front

(Always run/trace through the actual algorithm to confirm exact output strings before an interview — don't trust hand-traced examples blindly.)

How interviewers phrase it

• "Given a string s, you can add characters only at the front. Return the shortest palindrome you can form."
• This is LeetCode 214 — a classic "Hard" tagged problem, frequently used to test whether you actually understand KMP or just memorized it for pattern matching.
• Interviewers sometimes start you off with "Min chars to make palindrome" as a warm-up, then escalate to this exact problem expecting you to construct the full string.

Clarifying questions to ask

1. Can I insert at the back too, or strictly the front only? (Strictly front-only — confirm this since "shortest palindrome" problems vary.)
2. Can I insert any characters, or only characters already present in s? (Doesn't change the length of the answer, but does change what string you'd construct if there were any ambiguity — though here the answer is actually deterministic regardless.)
3. Is the output expected to be the full final palindrome string, or just the prepended part? (Most variants want the full final string — confirm.)
4. What are constraints on string length? (LeetCode constraints: up to 5×10⁴ — signals you need O(n), not O(n²).)
5. Empty/null string handling expected?

Follow-ups to expect

1. "You've solved this with KMP — can you also solve it using Manacher's Algorithm?"
2. "Can you do this with Rabin-Karp / rolling hash instead?"
3. "What if insertions are allowed at the back instead of front?"
4. "What's the relationship between this problem and 'Longest Happy Prefix'?"
5. "Can you prove why the greedy approach (always taking the longest palindromic prefix) gives the globally shortest result?"

Related questions

• Minimum characters to make string palindrome Hard
• Longest happy prefix Hard
• Letter Combinations of a Phone Number Hard
• Palindrome partitioning Hard
• Expression Add Operators Hard
• Longest Repeating Character Replacement Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in