"Cracking the coding interview", strings, 1.4.2

cracking-the-coding-interview-1-4-2.js

/**
 * Проверяет является ли переданная строка
 * перестановкой палиндрома.
 * Работает за O(n) и не требует дополнительной памяти,
 * использует битовый вектор для хранения счетчиков.
 *
 * @param {string} str
 * @returns {boolean}
 */
function isPalindromePermutation(str) {
  const vector = createBitVector(str);
  return vector === 0 || (vector & (vector - 1)) === 0;
}

/**
 * Создает битовый вектор,
 * который соответствует указанной строке:
 * для каждого символа на определенной позиции в алфавите
 * переключается состояние бита на этой позиции.
 *
 * @param {string} str
 * @returns {number}
 */
function createBitVector(str) {
  let vector = 0;
  
  for (let i = 0; i < str.length; i++) {
    vector = toggle(vector, getCharIndex(str[i]));
  }
  return vector;
}

/**
 * Переключает один конкретный бит
 * на определенной позиции в векторе
 * 
 * @param {number} vector
 * @param {number} index
 * @returns {number}
 */
function toggle(vector, index) {
  if (index < 0) {
    return vector;
  }
  let mask = 1 << index;

  if ((vector & mask) === 0) {
    vector |= mask;
  } else {
    vector &= ~mask;
  }
  return vector;
}

/**
 * Возвращает порядковый номер индекса
 * в английском алфавите (от 0 до 25).
 * Если это не буква — вернется -1.
 * 
 * @param {string} char
 * @returns {number}
 */
function getCharIndex(char) {
  const index = char.toLowerCase().charCodeAt(0) - 'a'.charCodeAt(0);
  
  if (index < 0 || index > 25) {
    return -1;
  }
  return index;
}