# Given a string s, convert it into a palindrome

3.92K views
0

Given a string s, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

Example 1:

Input: "aacecaaa"
Output:"aaacecaaa"

Example 2:

Input: "abcd"
Output: "dcbabcd"

0

There are different edge cases we want to tackle in this sort of a problem

1. Check if the string contains all non-repeating characters, if that’s the case, prefix last N-1 characters from the string of length N in front of the string

2. If first criteria isn’t met, check the indices which differ in values in the string and save the first index. Reverse the sub-string ahead of this pivot and append the original string S to this substring obtained.

3. If both the above isn’t the case, then loop through the string in the reverse order, and append character/s one by one to a new string and append the original string to the new string and check for palindrome in the loop, if it’s  palindrome, return it else continue looping.

Javascript code below

/**
* @param {string} s
* @return {string}
*/
var shortestPalindrome = function(s) {
if (isPallindrome(s)) return s;
var match = s.match(/(?=^[A-Za-z0-9]+\$)(.)+.*\1.*/g);
if (!match) {
return s.substring(1).split('').reverse().join('') + s;
}
var pivot = -1;
for (var ii = 0; ii < s.length; ii++) {
if (s[ii] !== s[ii + 1]) {
pivot = ii;
break;
}
}
var string = s.substr(pivot + 1);
var rem = string.split('').reverse().join('');
if (pivot + 1 === Math.floor((s.length - 1) / 2))
return rem + s;
var preset = '';
for (var i = s.length - 1; i >= 0; i--) {
preset += s[i];
var str = preset + s;
if (isPallindrome(str))
return str;
}
};
var isPallindrome = function(strng) {
return [...strng].reverse().join('') === strng;
};

Changed status to publish