Link to Question

MEDIUM

3035. Maximum Palindromes After Operations

You are given a 0-indexed string array words of length n containing strings.

You are allowed to perform the following operation any number of times (including zero):

• Choose integers i, j, x, and y such that 0 <= i, j < n, 0 <= x < words[i].length, 0 <= y < words[j].length, and swap the characters words[i][x] and words[j][y].

Return an integer denoting the maximum number of palindromes words can contain, after performing some operations.

Note: i and j may be equal during an operation.

Example

Input:

words = ["abbb","ba","aa"]

Output:

3

Explanation: After swaps, all strings can be rearranged to be palindromes.

---

Input:

words = ["abc","ab"]

Output:

2

Explanation: After swaps, both strings can be rearranged to be palindromes.

---

Input:

words = ["cd","ef","a"]

Output:

1

Explanation: Only one string can be a palindrome.

---

Constraints

• 1 ≤ words.length ≤ 1000
• 1 ≤ words[i].length ≤ 100
• words[i] consists only of lowercase English letters.

---

Solution: Greedy + Counting

• Time Complexity: O(N * L), where N is the number of words and L is the average length.
• Space Complexity: O(1), for character counts.

C++

class Solution {
public:
    int maxPalindromesAfterOperations(vector<string>& words) {
        vector<int> lens;
        int freq[26] = {};
        for (auto& w : words) {
            lens.push_back(w.size());
            for (char c : w) freq[c - 'a']++;
        }
        sort(lens.begin(), lens.end());
        int pairs = 0;
        for (int i = 0; i < 26; ++i) pairs += freq[i] / 2;
        int res = 0;
        for (int len : lens) {
            int need = len / 2;
            if (pairs >= need) {
                pairs -= need;
                res++;
            } else break;
        }
        return res;
    }
};