Rearranging a string to be a palindrome

Tags:



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;

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.



Source: stackoverflow