Leetcode3035. 回文字符串的最大数量

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

结果：

复杂度分析：

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

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