Find shortest palindrome by adding minimum characters in front using KMP LPS.
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.
Examples
Input: s = "aacecaaa"
Output: "aaacecaaa"
Explanation: Combining the input according to Shortest Palindrome logic yields "aaacecaaa".
Input: s = "abcd"
Output: "dcbabcd"
Explanation: Combining the input according to Shortest Palindrome logic yields "dcbabcd".
Complexity
Time Complexity: O(N)
Space Complexity: O(N)
Hints
š” Hint 1:
Find the longest palindromic prefix of s.
š” Hint 2:
Construct a string temp = s + "#" + reverse(s).
š” Hint 3:
The LPS value of the last character of temp gives the length of the longest palindromic prefix. Prepend the remaining suffix in reverse.
Editorial & Approach
Problem Overview & Intuition
To add the minimum characters in front of s, we must find the longest prefix of s that is already a palindrome. Using KMP LPS on s + "#" + reverse(s), the last LPS value directly yields the length of this palindromic prefix in linear O(N) time.
Step-by-Step Approach
- Reverse
sintorev. - Form string
temp = s + "#" + rev. - Compute the LPS array for
temp. - Length of longest palindromic prefix is
k = lps[temp.length - 1]. - Prepend
rev.slice(0, s.length - k)tos. - Return result.
Optimal Implementation (JavaScript)
function shortestPalindrome(s) {
const rev = s.split('').reverse().join('');
const temp = s + '#' + rev;
const n = temp.length;
const lps = new Array(n).fill(0);
let len = 0, i = 1;
while (i < n) {
if (temp[i] === temp[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len !== 0) len = lps[len - 1];
else {
lps[i] = 0;
i++;
}
}
}
return rev.slice(0, s.length - lps[n - 1]) + s;
}Complexity Analysis
Time Complexity
O(N) ā KMP LPS preprocessing of string of length 2N + 1.
Space Complexity
O(N) ā LPS table storage.
Edge Cases & Corner Traps Handled
- Already a palindrome: returns unchanged.
- Empty string: returns "".
- All distinct characters: reverses all except first character.