Medium

题目描述

给你一个长度为 n 的字符串数组 words，数组中包含从 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] 仅由小写英文字母组成。

解题思路

思路分析

这道题的关键洞察是：我们可以在所有字符串之间自由重新分配字符。

核心思路：

  1. 统计总的字符频率：由于可以任意交换字符，我们先统计所有字符串中每个字符的总频次。

  2. 计算可用的字符对数：对于每个字符，freq[ch] / 2 表示可以形成的字符对数。这些字符对可以用来构成回文的对称部分。

  3. 贪心策略：按字符串长度从小到大排序，优先让短的字符串变成回文。这是因为：

    • 短字符串需要的字符对更少，更容易满足
    • 剩余的字符对可以用于更长的字符串

  4. 回文构造规则：

    • 长度为 len 的字符串需要 len / 2 个字符对
    • 如果长度为奇数，中间位置可以放任意字符（不需要配对）

  5. 贪心分配：对每个字符串，检查当前剩余的字符对是否足够。如果够，就将其变为回文并减少相应的字符对数；否则跳过。

算法步骤：

  1. 统计所有字符的频率
  2. 计算总的可用字符对数
  3. 按长度排序字符串
  4. 贪心地为每个字符串分配字符对
  5. 返回成功构造的回文数量

代码实现

class Solution {
public:
    int maxPalindromesAfterOperations(vector<string>& words) {
        vector<int> freq(26, 0);
        vector<int> lengths;
        
        // 统计字符频率和长度
        for (const string& word : words) {
            lengths.push_back(word.length());
            for (char c : word) {
                freq[c - 'a']++;
            }
        }
        
        // 计算总的字符对数
        int pairs = 0;
        for (int f : freq) {
            pairs += f / 2;
        }
        
        // 按长度排序
        sort(lengths.begin(), lengths.end());
        
        // 贪心分配
        int result = 0;
        for (int len : lengths) {
            int needed = len / 2;
            if (pairs >= needed) {
                pairs -= needed;
                result++;
            } else {
                break;
            }
        }
        
        return result;
    }
};

class Solution:
    def maxPalindromesAfterOperations(self, words: List[str]) -> int:
        from collections import Counter
        
        # 统计所有字符频率
        freq = Counter()
        lengths = []
        
        for word in words:
            lengths.append(len(word))
            for char in word:
                freq[char] += 1
        
        # 计算总的字符对数
        pairs = sum(count // 2 for count in freq.values())
        
        # 按长度排序
        lengths.sort()
        
        # 贪心分配
        result = 0
        for length in lengths:
            needed = length // 2
            if pairs >= needed:
                pairs -= needed
                result += 1
            else:
                break
        
        return result

public class Solution {
    public int MaxPalindromesAfterOperations(string[] words) {
        var freq = new int[26];
        var lengths = new List<int>();
        
        // 统计字符频率和长度
        foreach (string word in words) {
            lengths.Add(word.Length);
            foreach (char c in word) {
                freq[c - 'a']++;
            }
        }
        
        // 计算总的字符对数
        int pairs = 0;
        foreach (int f in freq) {
            pairs += f / 2;
        }
        
        // 按长度排序
        lengths.Sort();
        
        // 贪心分配
        int result = 0;
        foreach (int len in lengths) {
            int needed = len / 2;
            if (pairs >= needed) {
                pairs -= needed;
                result++;
            } else {
                break;
            }
        }
        
        return result;
    }
}

var maxPalindromesAfterOperations = function(words) {
    const freq = new Array(26).fill(0);
    const lengths = [];
    
    // 统计字符频率和长度
    for (const word of words) {
        lengths.push(word.length);
        for (const char of word) {
            freq[char.charCodeAt(0) - 97]++;
        }
    }
    
    // 计算总的字符对数
    let pairs = 0;
    for (const f of freq) {
        pairs += Math.floor(f / 2);
    }
    
    // 按长度排序
    lengths.sort((a, b) => a - b);
    
    // 贪心分配
    let result = 0;
    for (const len of lengths) {
        const needed = Math.floor(len / 2);
        if (pairs >= needed) {
            pairs -= needed;
            result++;
        } else {
            break;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

指标复杂度
时间复杂度O(n log n + L)，其中 n 是字符串数量，L 是所有字符串的总长度
空间复杂度O(n)，用于存储长度数组和字符频率统计

相关题目