Shortest Palindrome
Turn a string into the shortest palindrome by adding characters only in front, using the KMP prefix function to find the longest prefix that is already a palindrome.
Problem Understanding
Shortest Palindrome (LeetCode 214): given s, add characters only in front of it to make the shortest possible palindrome, and return that palindrome.
Examples: s = "aacecaaa" → "aaacecaaa"; s = "abcd" → "dcbabcd".
The Intuition: Keep the Palindrome Already There
The fewest characters to add means the longest part of s left alone:
- Find the longest prefix of s that is a palindrome.
- Mirror the rest of
sand put it in front. - Find that prefix in O(n) by running KMP's prefix function on
s + '#' + reverse(s).
The brute-force check of a single string is Valid Palindrome, and the same fast string matching appears in Find the Index of the First Occurrence in a String.
Interactive Walkthrough
t = s + # + REVERSE(s) · 17 CHARACTERS
BUILD t
t
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
prefix under i
lps
i
:
j
:
answer
:
t = s + "#" + reverse(s) = "aacecaaa#aaacecaa". lps[0] = 0
Next
t[1] = "a" = t[0]: the match grows, lps[1] = 1
s
Watch the lps row fill under t: i walks t, j marks the prefix character it is matched against, and mismatches fall back. Try Fall back to see j jump back to a shorter prefix and still find a match.
Dry Run Table
Input: s = "aacecaaa", t = "aacecaaa#aaacecaa" (17 characters).
| i | t[i] | lps[i] | How |
|---|---|---|---|
| 1 | a | 1 | matches t[0] |
| 2–4 | c, e, c | 0 | fall back to 0, no match |
| 5, 6 | a, a | 1, 2 | match |
| 7 | a | 2 | fall back to 1, then match |
| 8 | # | 0 | falls back to 0 |
| 9–16 | a a a c e c a a | 1, 2, 2, 3, 4, 5, 6, 7 | match (one fall-back at i = 11) |
lps[16] = 7: "aacecaa" is the longest palindromic prefix, so add "a" in front: "aaacecaaa".
The Solution Template
KMP prefix function on s + '#' + reverse(s).
Shortest Palindrome Code
1var shortestPalindrome = function(s) {2 const rev = [...s].reverse().join('');3 const t = s + '#' + rev;4 const lps = new Array(t.length).fill(0);5 for (let i = 1; i < t.length; i++) {6 let j = lps[i - 1];7 while (j > 0 && t[i] !== t[j]) j = lps[j - 1];8 if (t[i] === t[j]) j++;9 lps[i] = j;10 }11 const k = lps[t.length - 1];12 return rev.slice(0, s.length - k) + s;13};
Edge Cases & Common Mistakes
- Empty string: the answer is empty.
- Already a palindrome: lps ends at n and nothing is added.
- Forgetting the separator: for s = "aaa", t = "aaaaaa" would give lps 5, longer than s.
- Adding characters at the end: the problem only allows the front.
- O(n²) prefix checks: correct but too slow for 5 · 10^4 characters of all "a"s with one "b".
Summary
Compute KMP's lps for s + '#' + reverse(s); its last value k is the longest palindromic prefix of s. Return reverse(s[k:]) + s. O(n) time and space.
More practice: DSA interview questions with answers · patterns cheat sheet