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"
The problem involves converting a given string into a palindrome by adding characters to the beginning of the string. The goal is to determine the minimum number of characters that need to be added to achieve this.
The solution leverages the Longest Prefix Suffix (LPS) array, which captures the length of the longest prefix of a string that is also a suffix. By combining the string and its reverse with a delimiter, the LPS array helps identify the largest palindromic prefix in the string. This ensures the minimum number of characters are added to the front to complete the palindrome.
The reverse of the string plays a critical role, as it determines the characters that are missing to form a palindrome when compared to the original string.
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Compute the Longest prefix suffix array for the combined string
vector<int> computeLPS(string s) {
int n = s.size(); // size of string
// To store the longest prefix suffix
vector<int> LPS(n, 0);
// Iterate on the string
for(int i=1; i < n; i++) {
// For all possible lengths
for(int len = 1; len < i; len++) {
if(s.substr(0, len) == s.substr(i-len+1, len))
LPS[i] = len;
}
}
return LPS; // Return the computed LPS array
}
public:
/* Function to find the shortest palindrome by inserting
characters at the beginning of given string */
string shortestPalindrome(string s) {
// To store the reverse string
string revs = s;
reverse(revs.begin(), revs.end());
// Forming the combined string
string str = s + '$' + revs;
// Computing the LPS array
vector<int> lps = computeLPS(str);
// Calculating the answer
int ans = s.size() - lps.back();
/* Finding the smallest string to be
added in front of the given string */
string to_add = revs.substr(0, ans);
// Return the result
return to_add + s;
}
};
int main() {
string s = "aacecaaa";
// Creating an instance of the solution class
Solution sol;
// Function call to find all indices of pattern in text
string ans = sol.shortestPalindrome(s);
cout << ans << endl;
return 0;
}import java.util.*;
class Solution {
// Compute the Longest prefix suffix array for the combined string
private int[] computeLPS(String s) {
int n = s.length(); // size of string
// To store the longest prefix suffix
int[] LPS = new int[n];
// Iterate on the string
for (int i = 1; i < n; i++) {
// For all possible lengths
for (int len = 1; len < i; len++) {
if (s.substring(0, len).equals(s.substring(i - len + 1, i + 1))) {
LPS[i] = len;
}
}
}
return LPS; // Return the computed LPS array
}
/* Function to find the shortest palindrome by inserting
characters at the beginning of given string */
public String shortestPalindrome(String s) {
// To store the reverse string
StringBuilder revs = new StringBuilder(s);
revs.reverse();
// Forming the combined string
String str = s + "$" + revs;
// Computing the LPS array
int[] lps = computeLPS(str);
// Calculating the answer
int ans = s.length() - lps[lps.length - 1];
/* Finding the smallest string to be
added in front of the given string */
String toAdd = revs.substring(0, ans);
// Return the result
return toAdd + s;
}
public static void main(String[] args) {
String s = "aacecaaa";
// Creating an instance of the solution class
Solution sol = new Solution();
// Function call to find all indices of pattern in text
String ans = sol.shortestPalindrome(s);
System.out.println(ans);
}
}
class Solution:
# Compute the Longest prefix suffix array for the combined string
def computeLPS(self, s):
n = len(s) # size of string
# To store the longest prefix suffix
LPS = [0] * n
# Iterate on the string
for i in range(1, n):
# For all possible lengths
for length in range(1, i):
if s[:length] == s[i - length + 1: i + 1]:
LPS[i] = length
return LPS # Return the computed LPS array
# Function to find the shortest palindrome by inserting
# characters at the beginning of given string
def shortestPalindrome(self, s):
# To store the reverse string
revs = s[::-1]
# Forming the combined string
str_combined = s + '$' + revs
# Computing the LPS array
lps = self.computeLPS(str_combined)
# Calculating the answer
ans = len(s) - lps[-1]
# Finding the smallest string to be added in front of the given string
to_add = revs[:ans]
# Return the result
return to_add + s
if _name_ == "_main_":
s = "aacecaaa"
# Creating an instance of the solution class
sol = Solution()
# Function call to find all indices of pattern in text
ans = sol.shortestPalindrome(s)
print(ans)
class Solution {
// Compute the Longest prefix suffix array for the combined string
computeLPS(s) {
const n = s.length; // size of string
// To store the longest prefix suffix
const LPS = new Array(n).fill(0);
// Iterate on the string
for (let i = 1; i < n; i++) {
// For all possible lengths
for (let len = 1; len < i; len++) {
if (s.substring(0, len) === s.substring(i - len + 1, i + 1)) {
LPS[i] = len;
}
}
}
return LPS; // Return the computed LPS array
}
/* Function to find the shortest palindrome by inserting
characters at the beginning of given string */
shortestPalindrome(s) {
// To store the reverse string
const revs = s.split('').reverse().join('');
// Forming the combined string
const str = s + '$' + revs;
// Computing the LPS array
const lps = this.computeLPS(str);
// Calculating the answer
const ans = s.length - lps[lps.length - 1];
// Finding the smallest string to be added in front of the given string
const toAdd = revs.substring(0, ans);
// Return the result
return toAdd + s;
}
}
// Main
const s = "aacecaaa";
// Creating an instance of the solution class
const sol = new Solution();
// Function call to find all indices of pattern in text
const ans = sol.shortestPalindrome(s);
console.log(ans);
Time Complexity: O(N), as all operations are linear with respect to the input string.
Space Complexity: O(N), to store the reverse string, combined string and the LPS array.
Q: Why use s + "$" + rev_s instead of just s + rev_s?
A: The separator ($) prevents unwanted overlapping between s and rev_s.
Q: How does this differ from finding the longest palindromic substring?
A: We extend s by adding characters only to the beginning instead of searching within.
Q: How would you modify the approach to allow adding characters anywhere (not just at the start)?
A: Use Manacher’s algorithm to find the longest palindromic substring, then determine the shortest extension.
Q: Can we solve this using dynamic programming (DP)?
A: Yes, a DP table can store minimum insertions needed, but it runs in O(n^2) instead of O(n).