LeetCode 题解工作台
回文字符串的最大数量
给你一个下标从 0 开始的字符串数组 words ，数组的长度为 n ，且包含下标从 0 开始的若干字符串。 你可以执行以下操作 任意 次数（ 包括零次 ）： 选择整数 i 、 j 、 x 和 y ，满足 0 ， 0 ， 0 ， 交换 字符 words[i][x] 和 words[j][y] 。 返…
6
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
class Solution: def maxPalindromesAfterOperations(self, words: List[str]) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个下标从 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 <= 10001 <= words[i].length <= 100words[i]仅由小写英文字母组成。
解题思路
方法一
class Solution:
def maxPalindromesAfterOperations(self, words: List[str]) -> int:
s = mask = 0
for w in words:
s += len(w)
for c in w:
mask ^= 1 << (ord(c) - ord("a"))
s -= mask.bit_count()
words.sort(key=len)
ans = 0
for w in words:
s -= len(w) // 2 * 2
if s < 0:
break
ans += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if the candidate effectively uses greedy methods for maximizing palindromes.
- question_mark
Look for clear understanding of how to count and redistribute characters using hash tables.
- question_mark
Evaluate how well the candidate balances time complexity with the need for multiple character swaps.
常见陷阱
外企场景- error
Failing to properly account for global character counts and only focusing on individual words.
- error
Overcomplicating the solution by trying to optimize too early, missing simple swaps.
- error
Not considering edge cases where no swaps are needed, such as when all words are already palindromes.
进阶变体
外企场景- arrow_right_alt
Consider variations with different input constraints, such as allowing some fixed swaps or limiting the number of operations.
- arrow_right_alt
Modify the problem by introducing additional restrictions on swap operations (e.g., restricting which words can swap with which).
- arrow_right_alt
Expand the problem to count and return the exact words that can be palindromes after the operation.