题目描述：
给你一个下标从 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\le words.len \le 1000, 1\le words[i].len \le 100$
题解：
由于可以随意交换字母，先把所有字母都取出来，然后考虑如何填入各个字符串。如果一个奇数长度字符串最终是回文串，那么它正中间的那个字母填什么都可以。既然如此，不妨先把左右的字母填了，最后在往正中间填入字母。
可以统计奇数长度的字符串个数 $cntS$ ，这些字符串中间需要消耗一个字母，然后就全是偶数长度的字符串了。每次一个字符串需要使用 $words[i].len / 2 \times 2$ 个字母。
填的时候先从长度比较短的填起，可以填更多的字符串。
代码：
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
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 5e2 + 10;
const static int maxm = 1e5 + 10;
const static long long mod = 1e9 + 7;
const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
int maxPalindromesAfterOperations(vector<string> &words)
{
int n = words.size();
int cntS = 0, cntl = 0;
int len = 0;
sort(words.begin(), words.end(), [](const string &a, const string &b)
{ return a.length() < b.length(); });
int mask = 0;
for (int i = 0; i < n; ++i)
{
len += words[i].length();
for (auto &ch : words[i])
mask ^= (1 << (ch - 'a'));
}
len -= __builtin_popcount(mask);
int ans = 0;
for (int i = 0; i < n; ++i)
{
len -= words[i].length() / 2 * 2;
if (len < 0)
return ans;
ans++;
}
return ans;
}
};
|