Given a string s, convert it into a palindrome
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"
There are different edge cases we want to tackle in this sort of a problem
- 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; };