Skip to main content

214. Shortest Palindrome

hard

Prepend the fewest characters to make a string a palindrome. Cracked in linear time with a KMP failure-function trick on a clever concatenation.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

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

Examples

Example 1

Input
s = "aacecaaa"
Output
"aaacecaaa"

Example 2

Input
s = "abcd"
Output
"dcbabcd"

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

You need the LONGEST palindromic prefix of s — the suffix that lies outside it must be reversed and prepended.

Hint 2

Build t = s + '#' + reverse(s). The separator '#' (any character not in the alphabet) prevents overflow.

Hint 3

Run the KMP failure function on t. The last value is the length of the longest prefix of s that equals a suffix of reverse(s) — i.e. the longest palindromic prefix of s.

Solution approach

Reveal approach

Reduce to a KMP failure-function computation. Construct t = s + '#' + reverse(s) and compute its prefix-function array (pi). pi[-1] is the length L of the longest proper prefix of t that equals a suffix of t — which, by construction, is the longest palindromic prefix of s. The answer is reverse(s[L:]) + s. The separator '#' is critical so the matched prefix cannot extend past s into the reversed half. O(n) time and O(n) space for t and pi. A naive O(n^2) approach (check each prefix for palindromicity) times out at 5*10^4.

Complexity

Time
O(n)
Space
O(n)

Related patterns

  • kmp
  • string-matching
  • prefix-function

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google
  • Amazon

Practice these live with InterviewChamp.AI

Drill Shortest Palindrome and Strings problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →