说在前面
🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是出于什么原因，算法学习需要持续保持。
题目描述
给你一个下标从 0 开始的字符串数组 words ，数组的长度为 n ，且包含下标从 0 开始的若干字符串。
你可以执行以下操作 任意 次数（包括零次）：
- 选择整数
i、j、x和y，满足0 <= i, j < n，0 <= x < words[i].length，0 <= y < words[j].length，交换 字符words[i][x]和words[j][y]。
返回一个整数，表示在执行一些操作后，words 中可以包含的回文字符串的 最大 数量。
注意： 在操作过程中，i 和 j 可以相等。
示例 1：
输入： words = ["abbb","ba","aa"] 输出： 3 解释： 在这个例子中，获得最多回文字符串的一种方式是： 选择 i = 0, j = 1, x = 0, y = 0，交换 words[0][0] 和 words[1][0] 。words 变成了 ["bbbb","aa","aa"] 。 words 中的所有字符串都是回文。 因此，可实现的回文字符串的最大数量是 3 。
示例 2：
输入： words = ["abc","ab"] 输出： 2 解释： 在这个例子中，获得最多回文字符串的一种方式是： 选择 i = 0, j = 1, x = 1, y = 0，交换 words[0][1] 和 words[1][0] 。words 变成了 ["aac","bb"] 。 选择 i = 0, j = 0, x = 1, y = 2，交换 words[0][1] 和 words[0][2] 。words 变成了 ["aca","bb"] 。 两个字符串都是回文 。 因此，可实现的回文字符串的最大数量是 2。
示例 3：
输入： words = ["cd","ef","a"] 输出： 1 解释： 在这个例子中，没有必要执行任何操作。 words 中有一个回文 "a" 。 可以证明，在执行任何次数操作后，无法得到更多回文。 因此，答案是 1 。
提示：
1 <= words.length <= 10001 <= words[i].length <= 100words[i]仅由小写英文字母组成。
解题思路
这道题目主要考察的是贪心策略，我们要思考怎么操作才能得到最多的回文字符串，首先我们需要先明确一下回文字符串的定义：
回文字符串是指正读和反读都相同的字符串。换句话说，它从左到右读和从右到左读是一样的。例如，“level”、"radar"和"madam"都是回文字符串。回文字符串可以包含字母、数字或其他字符。
我们可以根据其长度将回文字符串分为两类：
- 1、长度为奇数
则其会有（length - 1） / 2 对相同字符，及一个单独的字符，当然，多对字符串之间可以是相同的，成对字符串和单独的那个字符串也可以是相同的。
- 2、长度为偶数
其会有 length / 2 对相同字符，多对字符串之间同样可以是相同的。
题目说的是我们可以交易任意两个位置的字符串的任意两个下标之间的字符，这里的两个位置可以是相同的，也就是说我们可以交换同一个字符串里不同下标的字符，换句话说，我们可以使用原有字符串的所有字符进行重组，只需要保证重组的每个字符串长度和原来的字符串长度一致就行。
知道这个之后我们便可以开始编写代码了：
1、统计各个字母出现
const cnt = new Array(26).fill(0); for (const word of words) { for (let i = 0; i < word.length; i++) { const ind = word[i].charCodeAt() - 97; cnt[ind]++; } }
2、统计成对及落单字母的数量
let d = 0, s = 0; for (let i = 0; i < cnt.length; i++) { if (cnt[i] % 2 === 0) d += cnt[i]; else { s += 1; d += cnt[i] - 1; } }
3、将原有字符串数组按字符串长度从小到大排序
为了得到更多的回文字符串，我们应该优先重组长度更小的字符串，这样的到的字符串数量也就越多。
words.sort((a, b) => a.length - b.length);
4、重组回文字符串
- 1、需要重组的回文字符串长度为偶数
我们需要使用 length 个成对字符来重组。
- 2、需要重组的回文字符串长度为奇数
我们需要使用 length - 1 个成对字符和一个单独字符来重组。单独字符用完的时候我们可以将一对成对字符当成两个单独字符来使用。
如果成对字符不够用的话则说明当前字符串及往后的所有字符串都无法重组为回文字符串，我们直接返回当前已经得到的回文字符串数量即可。
for (const word of words) { if (word.length % 2 === 0) { d -= word.length; } else { if (s <= 0) { d -= 2; s += 2; } d -= word.length - 1; s -= 1; } if (d < 0) return ind; ind++; }
AC代码
/** * @param {string[]} words * @return {number} */ var maxPalindromesAfterOperations = function (words) { const cnt = new Array(26).fill(0); for (const word of words) { for (let i = 0; i < word.length; i++) { const ind = word[i].charCodeAt() - 97; cnt[ind]++; } } let d = 0, s = 0; for (let i = 0; i < cnt.length; i++) { if (cnt[i] % 2 === 0) d += cnt[i]; else { s += 1; d += cnt[i] - 1; } } words.sort((a, b) => a.length - b.length); let ind = 0; for (const word of words) { if (word.length % 2 === 0) { d -= word.length; } else { if (s <= 0) { d -= 2; s += 2; } d -= word.length - 1; s -= 1; } if (d < 0) return ind; ind++; } return words.length; };
公众号
关注公众号『前端也能这么有趣』，获取更多有趣内容。
说在后面
🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『
前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。
