Determine whether the characters in a provided string can be rearranged to construct a palindrome

Solution # 1: Using character map

const isPermutationOfPalindrome = (phrase) => {
    // count the character occurences in the phrase
    const charMap = {};
    for(let currentChar of phrase.toLowerCase()) {
      if(currentChar >= 'a' && currentChar <= 'z') {   
        charMap[currentChar] = (charMap[currentChar] || 0) + 1;
      }
    }
    
    // count the number of odd counts in above character map
    let oddCount = 0;
    for(const count of Object.values(charMap)) {
        if(count % 2 === 1) {
            oddCount++;
        }
    }
    
    // check if there is more than one odd count occurence
    return oddCount <= 1;
};

Explanation

• Iterate through each character in the input phrase, and create a character map (charMap) to store the count of occurrences for each character.
• Iterate over the values in the charMap to count the number of characters with an odd count.
• Check if the count of characters with an odd occurrence (oddCount) is less than or equal to 1. If so, return true; otherwise, return false.

Time Complexity

• O(n), where n is the length of the input string (phrase). The time complexity is determined by the two loops: one to iterate through the characters in the phrase and another to iterate through the values in the charMap. Both loops have a linear relationship with the size of the input string.

Space Complexity

• O(k), where k is the number of unique characters in the input string. The space complexity is determined by the size of the charMap, which is proportional to the number of unique characters in the phrase.

Solution # 2: Using character array

const isPermutationOfPalindrome = (phrase) => {
  // count the character occurences in the phrase
  let countOdd = 0;
  const charArray = new Array(26).fill(0);
  for (const char of phrase.toLowerCase()) {
    const charCode = char.charCodeAt(0);
    if ('a'.charCodeAt(0) <= charCode && charCode <= 'z'.charCodeAt(0)) {
      const index = charCode - 'a'.charCodeAt(0);
      charArray[index] += 1;
      // increment countOdd if odd count is found
      if (charArray[index] % 2 === 1) {
        countOdd += 1;
      } else {
        countOdd -= 1;
      }
    }
  }

  return countOdd <= 1;
};

Explanation

• In this solution we use a string array instead of a hashmap to make it more space-efficient.
• Initialize countOdd to track characters with odd occurrences.
• Create charArray to count each character’s occurrences. Iterate through lowercase characters in the phrase, updating charArray.
• Increment countOdd for characters with odd counts; decrement for even counts.
• Return true if the total count of characters with odd occurrences is at most 1.

Time Complexity

• O(n), where n is the length of the input string (phrase). The time complexity is determined by the loop iterating through the characters in the phrase. 

Space Complexity

• O(1) (constant space), as the size of charArray is fixed and independent of the input.

Comparison of two solutions

• Both algorithms have the same time complexity, O(n), where n is the length of the input string. However, the space complexity differs.
• The char code array version has a constant space complexity of O(1), while the hashmap version has a space complexity of O(k), where k depends on the number of unique characters in the input.
• In scenarios, where the input string has a limited set of characters, the char code array version might be more space-efficient. The hashmap version, on the other hand, is more versatile and can handle inputs with a larger number of unique characters.