214. Shortest Palindrome
Shortest Palindrome (LeetCode 214) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the String Manipulation Patterns pattern, in the Naive / KMP / Rabin-Karp subpattern.
How to solve Shortest Palindrome
Shortest Palindrome is a String Matching problem, part of String Manipulation Patterns. Master string matching algorithms including naive search, KMP pattern matching, and Rabin-Karp hashing.
Work towards the solution in these steps:
- Consider the problem as finding a way to extend the string by adding characters in front to form a palindrome; think about palindrome properties and how string prefixes relate to suffixes.
- Try to identify the longest palindromic prefix of the string since adding characters beyond that prefix will help complete the palindrome with minimal additions.
- Reflect on how string matching algorithms, especially those that preprocess patterns like KMP, can help find overlaps between the original string and its reversed version efficiently.
The reference solution runs in O(n) time and O(n) space.
The Shortest Palindrome solution and editorial walks through the full approach with reference code.
Problem statement
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 104
- s consists of lowercase English letters only.
Topics and companies
Topics: String, Rolling Hash, String Matching, Hash Function.
Reported in interviews at Microsoft.
How to practise Shortest Palindrome on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(n) space.
Open Shortest Palindrome in the code editor, or read the Shortest Palindrome editorial for a worked solution with its approach and complexity analysis.
Where Shortest Palindrome sits in the DSA pattern sheet
- String Manipulation Patterns pattern guide
- Naive / KMP / Rabin-Karp subpattern
- The full DSA patterns sheet
Problems related to Shortest Palindrome
Other problems that use the same Naive / KMP / Rabin-Karp and String Manipulation Patterns techniques:
- Find Beautiful Indices in the Given Array II — Hard, same subpattern
- Find the Index of the First Occurrence in a String — Easy, same subpattern
- Longest Common Prefix — Easy, same subpattern
- Repeated String Match — Medium, same subpattern
- Rotate String — Easy, same subpattern
- Add Strings — Easy, same pattern
Shortest Palindrome FAQ
What is the LeetCode number of Shortest Palindrome?
Shortest Palindrome is LeetCode problem 214, rated Hard.
What pattern is used to solve Shortest Palindrome?
Shortest Palindrome is a String Matching problem. It belongs to the String Manipulation Patterns pattern, in the Naive / KMP / Rabin-Karp subpattern.
What is the time complexity of Shortest Palindrome?
The reference solution runs in O(n) time and O(n) space.
Which companies ask Shortest Palindrome?
Shortest Palindrome has been reported in interviews at Microsoft.