JavaScript：如何求出字符串中字符拼凑出的回文串的最少个数？

Question

最近一次考试，遇到一道和回文相关的编程题，当场放弃了。题目如下：提供一个字符串s，其中每个字符都是小写字母。并提供字符串长度。要求：输字符串s中元素拼凑出的回文串的最小个数。其中，每个字符只能使用一次。*例如：s=“abbaa”，输出1，因为最少可以拼凑出“ababa”这一个回文串。s=“abc”，输出3，因为最少只能拼凑出“a”，“b”，“c”这三个回文串。*事后个人分析，判断回文功能的代码容易实现。较难实现的部分：1.拼凑出回文2.求出拼凑出的回文串的最小个数。望大神们提供下思路和方法~若能有实现代码，万分感谢~

Answer 1

只需求奇数个的个数即可，因为偶数可以附加到l两边；为 0 的话如果字符串不为空就是 1，因为偶数个总可以凑出一个。

function count (str) {

  str = String(str)

  if (!str) { return 0 }

  var nums = str.split('').reduce((map, s) => map.set(s, (map.get(s) || 0) + 1), new Map())

  return Array.from(nums.values()).reduce((odd, n) => n % 2 !== 0 ? odd + 1 : odd, 0) || 1

}

进一步简化

function count (str) {

  var arr = String(str).split('')

  if (arr.length <= 0) { return 0 }

  return arr.reduce((set, s) => set.delete(s) ? set : set.add(s), new Set()).size || 1

}