Skip to content

Instantly share code, notes, and snippets.

@Gerst20051
Last active September 8, 2021 10:48
Show Gist options
  • Save Gerst20051/345d6100686b488ba78d298b6da812e0 to your computer and use it in GitHub Desktop.
Save Gerst20051/345d6100686b488ba78d298b6da812e0 to your computer and use it in GitHub Desktop.
Palindrome Creator
function PalindromeCreator(str) {
const isStringPalindrome = isPalindrome(str);
if (isStringPalindrome) return 'palindrome';
const palindrome = findPalindrome([{
str,
chars: [],
}], 2, 0);
return palindrome && palindrome.str.length > 2 ? getRemovedCharsForPalindrome(palindrome) : 'not possible';
}
function isPalindrome(str) {
return str === str.split('').reverse().join('');
}
function findPalindrome(combinations, maxCharsToRemove, currentNumCharsRemoved) {
const allNewCombinations = [];
for (let i = 0; i < combinations.length; i++) {
const newCombinations = getCombinationsRemovingOneCharacter(combinations[i]);
const palindrome = newCombinations.find(combination => isPalindrome(combination.str));
if (palindrome) return palindrome;
allNewCombinations.push(...newCombinations);
}
if (currentNumCharsRemoved < maxCharsToRemove - 1) {
const palindrome = findPalindrome(allNewCombinations, maxCharsToRemove, currentNumCharsRemoved + 1);
if (palindrome) return palindrome;
}
}
function getCombinationsRemovingOneCharacter(combination) {
const combinations = [];
const { str, chars } = combination;
for (let i = 0; i < str.length; i++) {
combinations.push({
str: str.slice(0, i) + str.slice(i + 1),
chars: [...chars, {
char: str.slice(i, i + 1),
index: i,
}],
});
}
return combinations;
}
function getRemovedCharsForPalindrome(palindrome) {
return palindrome.chars.sort((a, b) => a.index - b.index).map(char => char.char).join('');
}
console.log(PalindromeCreator('mmop')); // not possible
console.log(PalindromeCreator('kjjjhjjj')); // k
console.log(PalindromeCreator('abjchba')); // jc
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment