回文字符串的最大数量

难度: Medium

给你一个下标从 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：

输入：words = ["abbb","ba","aa"]
输出：3
解释：在这个例子中，获得最多回文字符串的一种方式是：
选择 i = 0, j = 1, x = 0, y = 0，交换 words[0][0] 和 words[1][0] 。words 变成了 ["bbbb","aa","aa"] 。
words 中的所有字符串都是回文。
因此，可实现的回文字符串的最大数量是 3 。

示例 2：

输入：words = ["abc","ab"]
输出：2
解释：在这个例子中，获得最多回文字符串的一种方式是： 
选择 i = 0, j = 1, x = 1, y = 0，交换 words[0][1] 和 words[1][0] 。words 变成了 ["aac","bb"] 。
选择 i = 0, j = 0, x = 1, y = 2，交换 words[0][1] 和 words[0][2] 。words 变成了 ["aca","bb"] 。
两个字符串都是回文 。
因此，可实现的回文字符串的最大数量是 2。

示例 3：

输入：words = ["cd","ef","a"]
输出：1
解释：在这个例子中，没有必要执行任何操作。
words 中有一个回文 "a" 。
可以证明，在执行任何次数操作后，无法得到更多回文。
因此，答案是 1 。

提示：

1 <= words.length <= 1000
1 <= words[i].length <= 100
words[i] 仅由小写英文字母组成。

Submission

运行时间: 62 ms

内存: 17.1 MB

class Solution:
    def maxPalindromesAfterOperations(self, words: List[str]) -> int:
        ans = 0
        count = 0
        for x in Counter("".join(words)).values():
            count += x // 2
        for pi in sorted([len(word) for word in words]):
            if count >= pi // 2:
                count -= pi // 2
                ans += 1
        return ans

Explain

题解的思路是首先合并所有字符串，计算所有字符的总频数，然后计算可以组成多少对字符（每对字符可以在回文中形成镜像对）。接着，对words中的每个字符串，检查是否有足够的字符对来构成回文（考虑每个字符串的一半长度所需的字符对）。如果可以，就将这个字符串计为可能转换为回文的字符串，否则跳过。这种方法的关键在于通过字符的全局交换来最大化回文字符串的数量，而不是局限于单个字符串内部的调整。

时间复杂度: O(N + W log W)

空间复杂度: O(W)

class Solution:
    def maxPalindromesAfterOperations(self, words: List[str]) -> int:
        ans = 0  # 初始化回文字符串的数量
        count = 0  # 可用于形成回文的字符对的总数
        # 计算所有字符的总频数
        for x in Counter(\"\".join(words)).values():
            count += x // 2  # 每两个相同的字符可以形成一个字符对
        # 对每个单词的长度进行排序处理
        for pi in sorted([len(word) for word in words]):
            if count >= pi // 2:  # 检查是否有足够的字符对来构成当前字符串的一半
                count -= pi // 2
                ans += 1  # 成功构成一个回文
        return ans  # 返回可以形成的最大回文字符串数量

Explore

合并所有字符串并计算总频数是为了最大化使用字符的可能性，使得可以构成的回文字符串数量最大。如果单独对每个字符串进行统计，可能会因为每个字符串内字符的局限性而无法形成更多的回文字符串。例如，一个字符串中有多余的字符，而另一个字符串中正缺少这些字符以形成回文。通过合并字符串并统计总频数，可以跨字符串调配这些字符，从而增加形成回文的潜在数量。

是的，按照题解的逻辑，每两个相同的字符才能形成一个回文中的字符对。因此，任何字符的奇数部分在计算可以形成回文的字符对时会被剩余。这部分字符不能有效地用于形成字符对，因此在计算可用于构成回文的字符对的总数时会被忽略。然而，在实际构成回文字符串的过程中，这些奇数部分的字符可能用于位于回文中心的单个字符。

对字符串长度进行排序的目的是优先处理较短的字符串，因为它们需要较少的字符对来形成回文。这种策略确保了在有限的字符对资源下，能够尽可能多地构成回文字符串。从短到长处理字符串，可以在不耗尽字符对的情况下，最大化回文数量，因为处理长字符串时可能会由于字符对不足而无法构成回文，而较短的字符串更容易满足条件。