Shortest Palindrome solution and explanation
Google
9 more videos on this problem
Rabin Karp - Shortest Palindrome - Leetcode 214NeetCodeIO · 22:07 · 33K views
Shortest Palindrome | Multiple Ways | KMP Zindabaad | Leetcode 214 | codestorywithMIKcodestorywithMIK · 36:39 · 21K views
214.Shortest Palindrome || Leetcode || Solved&Explained || C++Aanchal Jain · 14:50 · 10K views
Shortest Palindrome | Leetcode 214Techdose · 16:13 · 10K views
Leetcode 214 Shortest Palindrome using KMP and Z Algorithms | String Matching Practice ProblemsBharat Khanna · 26:10 · 5K views
【每日一题】LeetCode 214. Shortest Palindrome, 8/30/2021Huifeng Guan · 32:52 · 1K views
LeetCode 214.Shortest Palindrome Solutionfei yufan · 22:17 · 1K views
Leetcode Question 214 "Shortest Palindrome" in PythonGhumman Tech · 3:28 · 578 views
214. Shortest Palindrome| Leetcode Problem|#leetcode #javaSawan kumar · 6:56 · 466 views
LeetCode 214. Shortest Palindrome — 48 msGarrett Smith · 36:23 · 389 views
The 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.
Example 1:
Input: s = "aacecaaa" Output: "aaacecaaa"
Example 2:
Input: s = "abcd" Output: "dcbabcd"
Constraints:
0 <= s.length <= 5 * 104sconsists of lowercase English letters only.
Approach overview
Problem Overview: Given a string s, add characters only to the front so the entire string becomes a palindrome. The goal is to produce the shortest possible palindrome after the insertion.
Approach 1: Brute Force Prefix Check (O(n^2) time, O(1) space)
This method searches for the longest prefix of s that is already a palindrome. Iterate from the full length down to 0 and check whether s[0..i] forms a palindrome using two pointers from both ends. Once you find the longest palindromic prefix, reverse the remaining suffix and prepend it to the original string. The palindrome check runs in O(n) and is repeated up to n times, giving O(n^2) time overall with constant extra space.
This approach is straightforward and useful for understanding the structure of the problem. However, repeated palindrome checks make it inefficient for large inputs.
Approach 2: KMP-Based Prefix Matching (O(n) time, O(n) space)
The optimized solution converts the problem into a prefix-suffix matching task using the Knuth-Morris-Pratt algorithm from string matching. The key observation: you need the longest prefix of s that is also a palindrome. Construct a new string t = s + '#' + reverse(s). Then compute the KMP prefix function (LPS array) for t.
The final value in the LPS array tells you the length of the longest prefix of s that matches a suffix of reverse(s). This effectively identifies the longest palindromic prefix. Take the remaining suffix of s, reverse it, and prepend it to form the shortest palindrome. Building the LPS array takes linear time, so the entire algorithm runs in O(n) time and uses O(n) extra space.
This approach relies on prefix overlap detection, a core idea in string algorithms. Some implementations also use rolling hash or other hash function techniques to detect palindromic prefixes, but KMP guarantees deterministic O(n) performance.
Recommended for interviews: The KMP-based approach is the expected optimal solution because it reduces repeated palindrome checks to a single linear preprocessing step. Brute force demonstrates understanding of the palindrome prefix property, but interviewers typically look for the KMP insight or an equivalent linear-time string matching technique.
Approach 1: Brute Force Method
The brute force approach involves checking each prefix of the string to determine if it forms a palindrome. We progressively add characters from the end of the string to the beginning until a valid palindrome is formed.
def shortestPalindrome(s):
if s == s[::-1]:
return s
for i in range(len(s) - 1, -1, -1):
if s[:i] == s[:i][::-1]:
return s[i:][::-1] + s
return ""#include <string>
std::string shortestPalindrome(std::string s) {
std::string rev_s = std::string(s.rbegin(), s.rend());
for (int i = s.size(); i >= 0; i--) {
if (s.substr(0, i) == rev_s.substr(s.size() - i)) {
return rev_s.substr(0, s.size() - i) + s;
}
}
return "";
}In this Python solution, we start by checking if the entire string s is already a palindrome. If it is, we return it immediately. Otherwise, we iteratively reduce the considered prefix of s and check if it forms a palindrome. Once a palindromic prefix is found, we append the reverse of the unmatched suffix before s.
Time Complexity: O(n^2), where n is the length of the string, due to the repeated palindrome checks.
Space Complexity: O(n) for storing the reversed string.
Approach 2: Optimized KMP-based Method
This approach uses the KMP (Knuth-Morris-Pratt) algorithm's partial match table (LPS array) to efficiently find the largest palindromic prefix. We concatenate the string with its reverse and compute the LPS array for substring match optimization.
public class Solution {
public String shortestPalindrome(String s) {
String temp = s + '#' + new StringBuilder(s).reverse().toString();
int[] lps = computeLPSArray(temp);
int palindromeLen = lps[lps.length - 1];
String suffixToAdd = new StringBuilder(s.substring(palindromeLen)).reverse().toString();
return suffixToAdd + s;
}
private int[] computeLPSArray(String s) {
int n = s.length();
int[] lps = new int[n];
int length = 0;
int i = 1;
while (i < n) {
if (s.charAt(i) == s.charAt(length)) {
length++;
lps[i] = length;
i++;
} else {
if (length != 0) {
length = lps[length - 1];
} else {
lps[i] = 0;
i++;
}
}
}
return lps;
}
}function shortestPalindrome(s) {
const sRev = s.split('').reverse().join('');
const new_s = s + '#' + sRev;
const lps = Array(new_s.length).fill(0);
let len = 0, i = 1;
while (i < new_s.length) {
if (new_s[i] == new_s[len]) {
len++;
lps[i] = len;
i++;
} else if (len > 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
}
const palinLength = lps[lps.length - 1];
return sRev.slice(0, s.length - palinLength) + s;
}In this Java solution, the string is concatenated with a separator and its reverse to form temp. The LPS array is used to find the longest prefix which is also a palindrome. We then reverse the remaining suffix of the original string and prepend it to s to produce the shortest palindrome.
Time Complexity: O(n), where n is the length of the string, due to linear time computation of the LPS array.
Space Complexity: O(n) for the LPS array and interim reversed string.
Approach 3: Default Approach
public class Solution {
public string ShortestPalindrome(string s) {
int baseValue = 131;
int mul = 1;
int mod = (int)1e9 + 7;
int prefix = 0, suffix = 0;
int idx = 0;
int n = s.Length;
for (int i = 0; i < n; ++i) {
int t = s[i] - 'a' + 1;
prefix = (int)(((long)prefix * baseValue + t) % mod);
suffix = (int)((suffix + (long)t * mul) % mod);
mul = (int)(((long)mul * baseValue) % mod);
if (prefix == suffix) {
idx = i + 1;
}
}
if (idx == n) {
return s;
}
return new string(s.Substring(idx).Reverse().ToArray()) + s;
}
}func shortestPalindrome(s string) string {
n := len(s)
base, mod := 131, int(1e9)+7
prefix, suffix, mul := 0, 0, 1
idx := 0
for i, c := range s {
t := int(c-'a') + 1
prefix = (prefix*base + t) % mod
suffix = (suffix + t*mul) % mod
mul = (mul * base) % mod
if prefix == suffix {
idx = i + 1
}
}
if idx == n {
return s
}
x := []byte(s[idx:])
for i, j := 0, len(x)-1; i < j; i, j = i+1, j-1 {
x[i], x[j] = x[j], x[i]
}
return string(x) + s
}impl Solution {
pub fn shortest_palindrome(s: String) -> String {
let base = 131;
let (mut idx, mut prefix, mut suffix, mut mul) = (0, 0, 0, 1);
for (i, c) in s.chars().enumerate() {
let t = (c as u64) - ('0' as u64) + 1;
prefix = prefix * base + t;
suffix = suffix + t * mul;
mul *= base;
if prefix == suffix {
idx = i + 1;
}
}
if idx == s.len() {
s
} else {
let x: String = (&s[idx..]).chars().rev().collect();
String::from(x + &s)
}
}
}Approach 4: KMP Algorithm
According to the problem description, we need to reverse the string s to obtain the string rev, and then find the longest common part of the suffix of the string rev and the prefix of the string s. We can use the KMP algorithm to concatenate the string s and the string rev and find the longest common part of the longest prefix and the longest suffix.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string s.
function shortestPalindrome(s: string): string {
const rev = s.split('').reverse().join('');
const t = s + '#' + rev + '$';
const n = t.length;
const next: number[] = Array(n).fill(0);
next[0] = -1;
for (let i = 2, j = 0; i < n; ) {
if (t[i - 1] === t[j]) {
next[i++] = ++j;
} else if (j > 0) {
j = next[j];
} else {
next[i++] = 0;
}
}
return rev.slice(0, -next[n - 1]) + s;
}public class Solution {
public string ShortestPalindrome(string s) {
char[] t = (s + "#" + new string(s.Reverse().ToArray()) + "$").ToCharArray();
int n = t.Length;
int[] next = new int[n];
next[0] = -1;
for (int i = 2, j = 0; i < n;) {
if (t[i - 1] == t[j]) {
next[i++] = ++j;
} else if (j > 0) {
j = next[j];
} else {
next[i++] = 0;
}
}
return new string(s.Substring(next[n - 1]).Reverse().ToArray()).Substring(0, s.Length - next[n - 1]) + s;
}
}func shortestPalindrome(s string) string {
t := s + "#" + reverse(s) + "$"
n := len(t)
next := make([]int, n)
next[0] = -1
for i, j := 2, 0; i < n; {
if t[i-1] == t[j] {
j++
next[i] = j
i++
} else if j > 0 {
j = next[j]
} else {
next[i] = 0
i++
}
}
return reverse(s)[:len(s)-next[n-1]] + s
}
func reverse(s string) string {
t := []byte(s)
for i, j := 0, len(t)-1; i < j; i, j = i+1, j-1 {
t[i], t[j] = t[j], t[i]
}
return string(t)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Method | Time Complexity: O(n^2), where |
| Optimized KMP-based Method | Time Complexity: O(n), where |
| Default Approach | – |
| KMP Algorithm | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Prefix Palindrome Check | O(n^2) | O(1) | Good for understanding the problem or when input sizes are small |
| KMP-Based Prefix Matching | O(n) | O(n) | Best general solution; avoids repeated palindrome checks |
Frequently asked questions
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.