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.This problem asks to find the shortest palindrome that can be formed by adding characters to the beginning of a given string. Two main approaches are commonly used: a rolling hash approach and a KMP (Knuth-Morris-Pratt) algorithm approach.
This approach efficiently finds the longest palindrome prefix of the input string. The core idea is to use a rolling hash to compare prefixes and suffixes of the string.
Algorithm:
Rolling Hash: A rolling hash function efficiently calculates the hash of a substring without recomputing the entire hash each time. We use a base (e.g., 131) and a modulus (e.g., 109 + 7) to prevent hash collisions.
Prefix and Suffix Hash: The algorithm calculates the rolling hash for prefixes and suffixes simultaneously. If the prefix and suffix hashes match up to a certain index idx
, it indicates that the substring from 0 to idx
is a palindrome.
Shortest Palindrome Construction: If idx
equals the string length, the string is already a palindrome. Otherwise, the shortest palindrome is formed by reversing the remaining suffix (s[idx:]
) and prepending it to the original string.
Time Complexity: O(n), where n is the length of the string. The rolling hash calculation iterates through the string once.
Space Complexity: O(1), as the algorithm uses only a constant amount of extra space.
This approach utilizes the KMP algorithm, typically used for string searching, to find the longest proper prefix that is also a suffix.
Algorithm:
String Concatenation: Concatenate the input string s
, a separator character (e.g., '#'), the reversed string s[::-1]
, and another separator (e.g., '$'). This creates a string t
.
KMP Next Array: Construct the KMP next
array for the concatenated string t
. The next
array stores the length of the longest proper prefix of a given substring that is also a suffix.
Longest Common Prefix-Suffix: The value next[n-1]
(where n
is the length of t
) indicates the length of the longest proper prefix of t
that is also a suffix. This corresponds to the longest palindrome prefix of the original string s
.
Shortest Palindrome Construction: The shortest palindrome is constructed by taking the reversed substring of s
from the length of the longest common prefix-suffix to the end, and prepending it to the original string s
.
Time Complexity: O(n), where n is the length of the string. The KMP algorithm has a linear time complexity.
Space Complexity: O(n), due to the next
array used in the KMP algorithm.
Code Examples (Python):
Solution 1 (Rolling Hash):
class Solution:
def shortestPalindrome(self, s: str) -> str:
base = 131
mod = 10**9 + 7
n = len(s)
prefix = suffix = 0
mul = 1
idx = 0
for i, c in enumerate(s):
prefix = (prefix * base + (ord(c) - ord('a') + 1)) % mod
suffix = (suffix + (ord(c) - ord('a') + 1) * mul) % mod
mul = (mul * base) % mod
if prefix == suffix:
idx = i + 1
return s if idx == n else s[idx:][::-1] + s
Solution 2 (KMP):
class Solution:
def shortestPalindrome(self, s: str) -> str:
t = s + "#" + s[::-1] + "$"
n = len(t)
next = [0] * n
next[0] = -1
i, j = 2, 0
while i < n:
if t[i - 1] == t[j]:
j += 1
next[i] = j
i += 1
elif j:
j = next[j]
else:
next[i] = 0
i += 1
return s[::-1][: -next[-1]] + s
Both solutions provide efficient ways to solve the shortest palindrome problem, each with its own advantages in terms of space complexity. The rolling hash solution is generally preferred for its better space efficiency. However, the KMP approach offers a different algorithmic perspective and can be valuable for understanding string manipulation techniques.