I’m trying to solve the problem of: Given an array of strings with only lower case letters, make a function that returns an array of those same strings, but each string has its letters rearranged such that it becomes a palindrome (if not possible then return -1). I’m a bit stuck on how I should be rearranging the letters.
let arr = ["hello", "racecra"]
;
I created a function to first check if a word is a palindrome :
function isPalindrome(arr) { let obj = {}; for (var x = 0; x < str.length; x++) { if (obj[arr[x]]) { obj[arr[x]] += 1; } else { obj[arr[x]] = 1; } } let countOdd = 0; let countEven = 0; for (let x of Object.values(obj)) { if (x % 2 == 0) { countEven += 1; } else { countOdd += 1; } } return countOdd == 1 ? true : false }
then I plan to loop through the words
let emptyArr = []; for (var x = 0; x < arr.length; x++) { if (isPalindrome(arr[x]) { // not sure what to do here. I know the word is a palindrome but not sure how to sort the order of the word in the palindrome form. } else { emptyArr.push(-1); } } return emptyArr;
Advertisement
Answer
Look closely: you don’t need your words to be palindromes, you need them to be rearrangeable as palindromes (“palindrome-candidates”). Now, a word is a palindrome-candidate if all of its letters but one can be counted by an even number (2, 4, 6 etc.)
For example, this…
hollo
… is NOT a palindrome, but can become one, as there’s 2 ‘o’, 2 ‘l’ and just one ‘h’ in it. To rearrange, you just move ‘h’ in the middle, then just place ‘o’ and ‘l’ before and after it:
l -> o -> h <- o <- l
So start with splitting each of your words by characters, then either count those characters or just sort them (as @Barmar suggested). If they satisfy the condition, rearrange the letters following the approach given; if not, return null (or any other special value clearly distinguishable from the rest) immediately.
Here’s one way to do it:
function rearrangeAsPalindrome(word) { if (word.length === 1) return word; // easy win first const charCounter = word.split('').reduce((counter, ch) => ({ ...counter, [ch]: (counter[ch] || 0) + 1 }), {}); const parts = ['', '', '']; // left, middle, right const entries = Object.entries(charCounter); for (let i = 0; i < entries.length; ++i) { const [char, counter] = entries[i]; if (counter % 2) { // odd if (parts[1] !== '') return null; // one odd is already here, eject! eject! parts[1] = char.repeat(counter); } else { // even const half = counter / 2; parts[0] = char.repeat(half) + parts[0]; parts[2] += char.repeat(half); } } return parts.join(''); } console.log(rearrangeAsPalindrome('racarrrac')); // crraaarrc console.log(rearrangeAsPalindrome('aabbcc')); // cbaabc console.log(rearrangeAsPalindrome('hollo')); // lohol console.log(rearrangeAsPalindrome('hello')); // null
This function returns null
(and does it early) when it realizes the word given cannot be rearranged as a palindrome – or an actual palindrome if it is possible.