• Leetcode 3035. Maximum Palindromes After Operations
  • 1. 解題思路
  • 2. 代碼實現(xiàn)

• 題目鏈接：3035. Maximum Palindromes After Operations

1. 解題思路

這一題的話因為可以任意交換，因此事實上要考察回文的最大個數(shù)，我們只需要統(tǒng)計所有單詞當(dāng)中字符出現(xiàn)的頻次，看看他們能組成多少回文即可。

而這部分，我們只需要統(tǒng)計所有的字符頻次當(dāng)中pair的個數(shù)和獨立元素的個數(shù)即可，且需要注意的是，如果獨立元素不夠用了，我們可以將成對的元素拆分為兩個獨立元素，即可滿足使用需求。

另外，要使得能組成的回文盡可能的多，我們應(yīng)該優(yōu)先匹配較短的單詞，這樣才能夠確保能夠組成最多的回文。

2. 代碼實現(xiàn)

給出python代碼實現(xiàn)如下：

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，占用內(nèi)存17.3MB。