Shortest Palindrome
OracleThe problem
Given a string s convert it into a palindrome by adding characters to the beginning of it. Return the shortest palindrome you can create by performing this transformation.
Input: s = "aacecaaa" Output: aaacecaaa Explanation: Adding "a" to the front of "aacecaaa" makes it a palindrome: "aaacecaaa".
Input: s = "race" Output: ecarace Explanation: By adding "eca" in front of "race", the shortest palindrome "ecarace" is formed.
Input: s = "abcd"
- 1 <= s.length <= 104
cpp
class Solution{
public:
string shortestPalindrome(string s) {
}
};java
class Solution {
public String shortestPalindrome(String s) {
}
}python
class Solution:
def shortestPalindrome(self, s: str) -> str:javascript
class Solution {
shortestPalindrome(s) {
}
}csharp
class Solution {
public string ShortestPalindrome(string s) {
}
}go
func shortestPalindrome(s string) string {
}Stuck? Show a way to structure it+
- 01Reverse the input.
- 02Concatenate original, a delimiter, and reversed.
- 03Compute its prefix function.
- 04Use the final value as longest palindromic prefix length.
- 05Prepend the unmatched reversed suffix.
Reference answer
Then expect these follow-ups
Can a rolling hash implement this with collision risk?
Tests: implementation extension
How would you build the shortest palindrome by appending instead?
Tests: follow-up reasoning
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question