Palindrome Permutation II

Description

null

Solution(javascript)

/**
 * @param {string} s
 * @return {string[]}
 */
const generatePalindromes = function (s) {
  const result = []

  const map = {}
  let oddCount = 0
  for (const c of s) {
    map[c] = map[c] || 0
    map[c] += 1
    if (map[c] % 2 === 0) {
      oddCount -= 1
    } else {
      oddCount += 1
    }
  }

  if (oddCount > 1) {
    return result
  }

  const aux = (map, left, right) => {
    const keys = Object.keys(map)
    if (keys.length === 0) {
      result.push(left + right)
      return
    }
    if (keys.length === 1) {
      let current = ''
      for (let i = 0; i < map[keys[0]]; i++) {
        current += keys[0]
      }
      result.push(left + current + right)
      return
    }
    for (const key of keys) {
      const newMap = { ...map }
      if (newMap[key] >= 2) {
        newMap[key] -= 2
        if (newMap[key] === 0) {
          delete newMap[key]
        }
        aux(newMap, left + key, key + right)
      }
    }
  }
  aux(map, '', '')
  return result
}