Every day a Leetcode

题目来源：3035. 回文字符串的最大数量

解法1：哈希 + 排序

由于可以随意交换字母，先把所有字母都取出来，然后考虑如何填入各个字符串。

如果一个奇数长度字符串最终是回文串，那么它正中间的那个字母填什么都可以。

既然如此，不妨先把左右的字母填了，最后在往正中间填入字母。

字符串越短，需要的字母越少。

所以按照字符串的长度从小到大填。

统计所有字符串的长度之和，减去出现次数为奇数的字母，即为可以往左右填入的字母个数 total。

把字符串按照长度从小到大排序，然后遍历。注意长为奇数的字符串，由于不考虑正中间的字母，其长度要减一。

代码：

/** @lc app=leetcode.cn id=3035 lang=cpp** [3035] 回文字符串的最大数量*/// @lc code=start
class Solution
{
public:int maxPalindromesAfterOperations(vector<string> &words){// 特判if (words.empty())return 0;int n = words.size();int total = 0; // 出现次数为偶数的字母总数unordered_map<char, int> mp;for (string &word : words){total += word.length();for (char &c : word)mp[c]++;}// 减去出现次数为奇数的字母for (auto &[ch, cnt] : mp)total -= cnt % 2;sort(words.begin(), words.end(), [](const string &s1, const string &s2){ return s1.length() < s2.length(); });int ans = 0;for (string &word : words){int len = word.length();// 长为奇数的字符串，长度要减一total -= len % 2 == 1 ? len - 1 : len;if (total < 0)break;ans++;}return ans;}
};
// @lc code=end

结果：

复杂度分析：

时间复杂度：O(L+nlogn)，其中 n 是数组 words 的长度，L 是数组 words 中字符串的总长度。

空间复杂度：O(|∑|)，其中 ∑ 是字符集，|∑| 为字符集的大小，因为 words[i] 仅由小写英文字母组成，所以 |∑|=26。