DSA problem

Shortest Palindrome

HardString MatchingPattern: String Matchingtop300GoogleAmazonMicrosoftPony.aiApple

You are given a string s. You can convert s to a palindrome by adding characters in front of it. Return the shortest palindrome you can find by performing this transformation. Only prepending is allowed — you may not modify or remove existing characters.

The problem reduces to finding the longest prefix of s that is itself a palindrome. Call that prefix P and let R be the suffix of s after P. Then reverse(R) + s is a palindrome and is provably the shortest one obtainable by prepending characters. Every character of R must be mirrored to the front because nothing on the existing side balances it; characters within P already balance themselves.

So the core sub-problem is: what is the longest palindromic prefix of s? A clean way to compute this is to use the KMP failure (LPS) array on the combined string s + '#' + reverse(s). The sentinel '#' (any character not in the alphabet) prevents matches from straddling the boundary. The last value of the LPS array on this combined string equals the length of the longest prefix of s that is also a suffix of reverse(s) — which is exactly the longest palindromic prefix of s.

Once that length L is known, the answer is reverse(s[L:]) + s. The combined string has length 2n + 1, so building the LPS array takes O(n) time and the final concatenation is O(n) as well. Total: O(n) time and O(n) space — far better than the obvious O(n^2) approach that checks every prefix for palindromicity.

Examples

Example 1

Input: s = "aacecaaa"

Output: "aaacecaaa"

Explanation: The longest palindromic prefix of "aacecaaa" is "aacecaa" (length 7). The single remaining character "a" reversed is "a", and prepending it gives "aaacecaaa", which is a palindrome.

Example 2

Input: s = "abcd"

Output: "dcbabcd"

Explanation: The longest palindromic prefix of "abcd" is just "a". The suffix "bcd" reversed is "dcb"; prepending it produces "dcbabcd".

Example 3

Input: s = "aba"

Output: "aba"

Explanation: The entire string "aba" is already a palindrome, so the longest palindromic prefix equals the whole string and nothing needs to be prepended.

Constraints

0 <= s.length <= 5 * 10^4
s consists of lowercase English letters.

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

stringstring-matchingkmppalindrome

Browse all DSA problems