Leetcode 3035. Maximum Palindromes After Operations

• Leetcode 3035. Maximum Palindromes After Operations
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3035. Maximum Palindromes After Operations

1. 解题思路

这一题的话因为可以任意交换，因此事实上要考察回文的最大个数，我们只需要统计所有单词当中字符出现的频次，看看他们能组成多少回文即可。

而这部分，我们只需要统计所有的字符频次当中pair的个数和独立元素的个数即可，且需要注意的是，如果独立元素不够用了，我们可以将成对的元素拆分为两个独立元素，即可满足使用需求。

另外，要使得能组成的回文尽可能的多，我们应该优先匹配较短的单词，这样才能够确保能够组成最多的回文。

2. 代码实现

给出python代码实现如下：

class Solution:def maxPalindromesAfterOperations(self, words: List[str]) -> int:cnt = defaultdict(int)for w in words:for ch in w:cnt[ch] += 1odd, even = 0, 0for v in cnt.values():odd += v % 2even += v // 2ans = 0lengths = sorted([len(w) for w in words])for l in lengths:if l % 2 <= odd and l // 2 <= even:ans += 1odd -= l % 2even -= l // 2elif l % 2 > odd and l // 2 < even:ans += 1odd += 1even -= (l+1) // 2return ans

提交代码评测得到：耗时130ms，占用内存17.3MB。