class Solution {
public:
int maxPalindromesAfterOperations(vector<string>& words) {
}
};
3035. 回文字符串的最大数量
给你一个下标从 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] 仅由小写英文字母组成。原站题解
golang 解法, 执行用时: 10 ms, 内存消耗: 6.3 MB, 提交时间: 2024-02-19 10:54:06
// 正向思维
func maxPalindromesAfterOperations(words []string) (ans int) {
tot, mask := 0, 0
for _, w := range words {
tot += len(w)
for _, c := range w {
mask ^= 1 << (c - 'a')
}
}
tot -= bits.OnesCount(uint(mask)) // 减去出现次数为奇数的字母
slices.SortFunc(words, func(a, b string) int { return len(a) - len(b) })
for _, w := range words {
tot -= len(w) / 2 * 2 // 长为奇数的字符串，长度要减一
if tot < 0 { break }
ans++
}
return
}
// 逆向思维
func maxPalindromesAfterOperations2(words []string) int {
oddL, mask := 0, 0
for _, w := range words {
oddL += len(w) % 2 // 统计奇数长度字符串个数
for _, c := range w {
mask ^= 1 << (c - 'a')
}
}
slices.SortFunc(words, func(a, b string) int { return len(b) - len(a) })
ans := len(words)
left := bits.OnesCount(uint(mask)) - oddL // S 中的剩余字母个数
for _, w := range words {
if left <= 0 { break }
left -= len(w) / 2 * 2
ans--
}
return ans
}
python3 解法, 执行用时: 162 ms, 内存消耗: 17.1 MB, 提交时间: 2024-02-19 10:53:09
class Solution:
# 逆向思维，有多少个字符串不是回文串
def maxPalindromesAfterOperations(self, words: List[str]) -> int:
odd_l = 0 # 奇数长度字符串个数
cnt = Counter()
for w in words:
odd_l += len(w) % 2
cnt += Counter(w)
words.sort(key=lambda w: -len(w)) # 按照长度从大到小排序
ans = len(words)
left = sum(c % 2 for c in cnt.values()) - odd_l # S 中的剩余字母个数
for w in words:
if left <= 0: break
left -= len(w) // 2 * 2
ans -= 1
return ans
python3 解法, 执行用时: 170 ms, 内存消耗: 17 MB, 提交时间: 2024-02-19 10:52:29
class Solution:
# 正向思维，填充
def maxPalindromesAfterOperations(self, words: List[str]) -> int:
ans = tot = 0
cnt = Counter()
for w in words:
tot += len(w) # 所有字符数量
cnt += Counter(w) # 所有字符出现频率
tot -= sum(c % 2 for c in cnt.values()) # 减去出现次数为奇数的字母
words.sort(key=len) # 按照长度从小到大排序
for w in words:
tot -= len(w) // 2 * 2 # 长为奇数的字符串，长度要减一
if tot < 0: break
ans += 1
return ans