Is Shortest Palindrome easy or hard?

Shortest Palindrome is classified as a Hard problem because recognizing the KMP transformation is not obvious. The brute force idea is simple, but deriving the linear-time string matching solution requires deeper knowledge of string algorithms.

Shortest Palindrome Python/Java solution

Python and C++ implementations often demonstrate the brute force or rolling hash approach, while Java and JavaScript solutions commonly implement the KMP prefix function to achieve O(n) time complexity.

How to solve Shortest Palindrome in O(n)?

Use a KMP-style prefix function. Create a new string s + '#' + reverse(s), compute the LPS array, and use the final value to determine the longest palindromic prefix. Reverse the remaining suffix and prepend it to the original string to build the result.

What is the best approach for Shortest Palindrome?

The most efficient approach uses the KMP string matching algorithm. By building a combined string of the original string and its reverse, you can compute the longest palindromic prefix using the LPS (prefix function) array. This reduces the problem to O(n) time with O(n) space.

Is Shortest Palindrome asked at Google/Amazon/Meta?

Shortest Palindrome and similar palindrome-prefix problems appear in interviews at large tech companies such as Google, Amazon, and Meta. They test understanding of string algorithms, especially KMP and palindrome detection techniques.

What data structure is used in Shortest Palindrome?

The problem primarily uses string processing techniques and arrays. The optimized solution relies on the KMP prefix table (LPS array) from string matching algorithms, while alternative approaches may use rolling hash with hash tables.

What is the time complexity of Shortest Palindrome?

The brute force approach runs in O(n^2) time because it repeatedly checks whether prefixes are palindromes. The optimized KMP-based solution runs in O(n) time by computing prefix matches in a single pass over the combined string.

Description Solution Video 22:07

214. Shortest Palindrome

Hard43.3% acceptance8 companies

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.

Example 1:

Input: s = "aacecaaa"
Output: "aaacecaaa"

Example 2:

Input: s = "abcd"
Output: "dcbabcd"

Constraints:

0 <= s.length <= 5 * 10⁴
s consists of lowercase English letters only.

Asked at 8 companies

Pocket Gems Accenture

Google Microsoft Meta Bloomberg Uber Amazon

Topics

22:07

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution

214. Shortest Palindrome

Asked at 8 companies

Topics

Similar problems