The problem. Given a string s, you may add letters in front of it only. Return the shortest palindrome you can make this way.
s = "aacecaaa" -> "aaacecaaa" (keep "aacecaa", add "a")
s = "abcd" -> "dcbabcd" (keep "a", add "dcb")
s = "racecar" -> "racecar" (already a palindrome)Whatever is added in front must mirror the end of s. So the best you can do is keep the longest prefix of s that is already a palindrome as the middle, and put the rest of s, reversed, in front. For "abcd" the longest palindrome prefix is just "a", so "dcb" goes in front: "dcbabcd".
Finding that prefix is the whole problem. Testing each prefix from longest to shortest is O(n²). KMP finds it in O(n) with one trick: a palindrome prefix P read backwards is still P, and it sits at the end of reverse(s). So P is a border of s + "#" + reverse(s) — a prefix that is also a suffix — and the KMP table's last entry gives the longest one. The # can't match any letter, so no border can be longer than s.
function shortestPalindrome(s) { const isPal = (end) => { // is s[0..end) a palindrome? for (let i = 0, j = end - 1; i < j; i++, j--) if (s[i] !== s[j]) return false; return true; }; let end = s.length; while (!isPal(end)) end--; // the longest palindrome prefix return [...s.slice(end)].reverse().join("") + s;}Time O(n²), space O(n). Up to n prefixes, each checked in up to n / 2 comparisons. Inputs like "aaaa…aaba…aaaa" hit the worst case: every check runs deep before failing.
Build the KMP table for s # reverse(s); its last entry is the longest palindrome at the start of s.
function shortestPalindrome(s) { const rev = [...s].reverse().join(""); const t = s + "#" + rev; // '#' stops a border from running past s const lps = new Array(t.length).fill(0); for (let i = 1, len = 0; i < t.length; ) { if (t[i] === t[len]) lps[i++] = ++len; else if (len > 0) len = lps[len - 1]; else lps[i++] = 0; } const keep = lps[t.length - 1]; // the longest prefix of s that is a palindrome return rev.slice(0, s.length - keep) + s; // mirror the rest onto the front}Time O(n), space O(n). One KMP table over 2n + 1 letters, then one slice. Why it's right: a border of length L has s[0..L) at the front of t and reverse(s[0..L)) at the back, so equal means s[0..L) is a palindrome — and the longest border is the longest such prefix.
This is the hardest lesson in the pattern because the reduction is the whole trick: once the question becomes longest border of s # reverse(s), KMP does the rest.
""."racecar" comes back unchanged."abcd" keeps only "a" and becomes "dcbabcd"."aaa", s + reverse(s) is "aaaaaa", whose border is 5 letters: longer than s, and the slice breaks.lps[n - 1].