Last updated on March 1st, 2025 at 08:50 pm
Here, we see the Shortest Palindrome LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
String
Companies
Google, Pocketgems
Level of Question
Hard
Shortest Palindrome LeetCode Solution
Table of Contents
1. 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”
2. Coding Pattern Used in Solution
The coding pattern used in all the provided implementations is “Palindromic Subsequence”. This pattern involves identifying or constructing palindromes by leveraging properties of symmetry and string manipulation. The goal is to find the shortest palindrome by appending characters to the beginning of the string.
3. Code Implementation in Different Languages
3.1 Shortest Palindrome C++
class Solution {
public:
string shortestPalindrome(string s) {
string t = process(s);
int n = t.length(), center = 0, right = 0;
int* palin = new int[n];
for (int i = 1; i < n - 1; i++) {
int i_mirror = 2 * center - i;
palin[i] = (right > i) ? min(palin[i_mirror], right - i) : 0;
while (t[i + palin[i] + 1] == t[i - palin[i] - 1])
palin[i]++;
if (i + palin[i] > right) {
center = i;
right = i + palin[i];
}
}
int pos;
for (int i = n - 2; i; i--) {
if (i - palin[i] == 1) {
pos = palin[i];
break;
}
}
string tail = s.substr(pos);
reverse(tail.begin(), tail.end());
return tail + s;
}
private:
string process(string& s) {
int n = s.length();
string t(2 * n + 3, '#');
t[0] = '$'; t[2 * n + 2] = '%';
for (int i = 0; i < n; i++)
t[2 * (i + 1)] = s[i];
return t;
}
};
3.2 Shortest Palindrome Java
class Solution {
public String shortestPalindrome(String s) {
int j = 0;
for (int i = s.length() - 1; i >= 0; i--) {
if (s.charAt(i) == s.charAt(j)) { j += 1; }
}
if (j == s.length()) { return s; }
String suffix = s.substring(j);
return new StringBuffer(suffix).reverse().toString() + shortestPalindrome(s.substring(0, j)) + suffix;
}
}
3.3 Shortest Palindrome JavaScript
var shortestPalindrome = function(s) {
var prefix = "";
var pos, head, tail;
for (pos = head = tail = parseInt(s.length / 2); pos > 0; head = tail = --pos) {
while (head !== 0 && s[head - 1] === s[head]) {
head--;
pos--;
}
while (tail != s.length - 1 && s[tail + 1] === s[tail]) {
tail++;
}
var isSame = true;
while (head >= 0) {
if (s[head] !== s[tail]) {
isSame = false;
break;
}
head--;
tail++;
}
if (isSame) {
break;
}
}
for (var k = s.length - 1; k >= tail && k !== 0; k--) {
prefix += s[k];
}
return prefix + s;
};
3.4 Shortest Palindrome Python
class Solution(object):
def shortestPalindrome(self, s):
r = s[::-1]
for i in range(len(s) + 1):
if s.startswith(r[i:]):
return r[:i] + s
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n) | O(n) |
| Java | O(n²) | O(n) |
| JavaScript | O(n²) | O(n) |
| Python | O(n²) | O(n) |
- C++ is the most efficient implementation due to the use of Manacher’s Algorithm, which reduces the time complexity to O(n).
- Java, JavaScript, and Python use simpler approaches but have higher time complexity (O(n²)) due to repeated substring operations or recursive calls.
- All implementations have O(n) space complexity, as they store intermediate results or reversed strings.