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 Sam K., 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

More Strings practice problems

See all Strings problems →