Shortest Palindrome — Solution in Python, Java & C++
Shortest Palindrome solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Shortest Palindrome is a hard coding problem on strings, rolling hash and KMP Algorithm, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Hard
- Topics: Strings, Rolling Hash, KMP Algorithm
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You may add characters in front of s to turn it into a palindrome.
Return the shortest palindrome you can make this way.
Example 1
Input: s = "aacecaaa"
Output: aaacecaaa
Explanation: The longest palindromic prefix is "aacecaa", so only one "a" needs prepending.
Example 2
Input: s = "abcd"
Output: dcbabcd
Explanation: Only "a" is a palindromic prefix, so "dcb" is prepended.
Example 3
Input: s = "kairo"
Output: oriakairo
Constraints
0 <= s.length <= 50000s consists of lowercase English letters.
Hints for Shortest Palindrome
Hint 1
You only ever prepend, so the tail of the answer is
sitself. The question is the length of the longest palindromic prefix ofs.Hint 2
Everything after that prefix has to be mirrored in front, reversed.
Hint 3
Finding the longest palindromic prefix is the same as finding the longest prefix of
sthat is also a suffix ofreverse(s)— which is exactly what KMP's failure function computes ons + "#" + reverse(s).
How to solve Shortest Palindrome
Let p be the longest palindromic prefix of s. The answer is reverse(s[p..]) + s, because everything beyond the prefix must be mirrored in front and nothing shorter can work. Computing p is a classic KMP trick.
Approach
- Build
combined = s + "#" + reverse(s). The separator#stops a match from spanning the two halves. - Run KMP's failure function over
combined. Its last value is the length of the longest prefix ofsthat is also a suffix ofreverse(s)— that is, the longest palindromic prefix ofs. - Call that length
keep. Prependreverse(s[keep..n-1])tos.
Why it works
A prefix of s equals a suffix of reverse(s) exactly when that prefix reads the same forwards and backwards. Any palindrome built by prepending must contain s as a suffix, so its first n - p characters are forced to mirror s[p..]; taking the longest palindromic prefix therefore minimises what is prepended.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Omitting the
#separator lets the failure function report a match longer thans, giving nonsense on inputs like"aaaa". - Checking each prefix for being a palindrome directly is O(n²) and times out at the stated limit.
- An empty input must return the empty string, not crash on
s[n-1].
Reference solution
Python
def shortestPalindrome(s: str) -> str:
n = len(s)
if n == 0:
return ""
combined = s + "#" + s[::-1]
fail = [0] * len(combined)
for i in range(1, len(combined)):
j = fail[i - 1]
while j > 0 and combined[i] != combined[j]:
j = fail[j - 1]
if combined[i] == combined[j]:
j += 1
fail[i] = j
keep = fail[-1]
return s[keep:][::-1] + sJava
public static String shortestPalindrome(String s) {
int n = s.length();
if (n == 0) return "";
String rev = new StringBuilder(s).reverse().toString();
String combined = s + "#" + rev;
int[] fail = new int[combined.length()];
for (int i = 1; i < combined.length(); i++) {
int j = fail[i - 1];
while (j > 0 && combined.charAt(i) != combined.charAt(j)) j = fail[j - 1];
if (combined.charAt(i) == combined.charAt(j)) j++;
fail[i] = j;
}
int keep = fail[combined.length() - 1];
return new StringBuilder(s.substring(keep)).reverse().toString() + s;
}C++
string shortestPalindrome(string s) {
int n = (int) s.size();
if (n == 0) return "";
string rev(s.rbegin(), s.rend());
string combined = s + "#" + rev;
vector<int> fail(combined.size(), 0);
for (size_t i = 1; i < combined.size(); i++) {
int j = fail[i - 1];
while (j > 0 && combined[i] != combined[j]) j = fail[j - 1];
if (combined[i] == combined[j]) j++;
fail[i] = j;
}
int keep = fail[combined.size() - 1];
string head = s.substr(keep);
reverse(head.begin(), head.end());
return head + s;
}JavaScript
var shortestPalindrome = function(s) {
var n = s.length;
if (n === 0) return "";
var rev = "";
for (var i = n - 1; i >= 0; i--) rev += s.charAt(i);
var combined = s + "#" + rev;
var fail = [];
for (var t = 0; t < combined.length; t++) fail.push(0);
for (var p = 1; p < combined.length; p++) {
var j = fail[p - 1];
while (j > 0 && combined.charAt(p) !== combined.charAt(j)) j = fail[j - 1];
if (combined.charAt(p) === combined.charAt(j)) j++;
fail[p] = j;
}
var keep = fail[combined.length - 1];
var head = "";
for (var q = n - 1; q >= keep; q--) head += s.charAt(q);
return head + s;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings