Problem

You are given a 0-indexed string array words having length n and containing 0-indexed 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 themaximum number of palindromes _words can contain, after performing some operations.

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

Examples

Example 1

1
2
3
4
5
6

Input: words = ["abbb","ba","aa"]
Output: 3
Explanation: In this example, one way to get the maximum number of palindromes is:
Choose i = 0, j = 1, x = 0, y = 0, so we swap words[0][0] and words[1][0]. words becomes ["bbbb","aa","aa"].
All strings in words are now palindromes.
Hence, the maximum number of palindromes achievable is 3.

Example 2

1
2
3
4
5
6
7

Input: words = ["abc","ab"]
Output: 2
Explanation: In this example, one way to get the maximum number of palindromes is: 
Choose i = 0, j = 1, x = 1, y = 0, so we swap words[0][1] and words[1][0]. words becomes ["aac","bb"].
Choose i = 0, j = 0, x = 1, y = 2, so we swap words[0][1] and words[0][2]. words becomes ["aca","bb"].
Both strings are now palindromes.
Hence, the maximum number of palindromes achievable is 2.

Example 3

1
2
3
4
5
6

Input: words = ["cd","ef","a"]
Output: 1
Explanation: In this example, there is no need to perform any operation.
There is one palindrome in words "a".
It can be shown that it is not possible to get more than one palindrome after any number of operations.
Hence, the answer is 1.

Constraints

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

Solution

Method 1 – Greedy Counting and Pairing

Intuition

Since we can swap any characters between any words, the total multiset of all characters is fixed. To maximize the number of palindromes, we want to distribute the characters so that as many words as possible can be rearranged into palindromes. A word can be rearranged into a palindrome if at most one character has an odd count. We can greedily pair up characters and assign them to words, giving each word as many pairs as possible, and then assign odd characters as centers if needed.

Approach

  1. Count the total frequency of each character across all words.
  2. For each word, record its length.
  3. Sort the word lengths in non-decreasing order.
  4. Count the total number of pairs and single (odd) characters available.
  5. For each word (from shortest to longest):
    • Assign as many pairs as possible to fill the word (each pair is two characters).
    • If the word length is odd and there are odd characters left, assign one as the center.
    • If not enough pairs or odd characters are left, stop.
  6. Return the number of words that can be made palindromic.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
public:
    int maxPalindromesAfterOperations(vector<string>& words) {
        vector<int> lens;
        vector<int> freq(26, 0);
        for (auto& w : words) {
            lens.push_back(w.size());
            for (char c : w) freq[c - 'a']++;
        }
        sort(lens.begin(), lens.end());
        int pairs = 0, odds = 0;
        for (int f : freq) {
            pairs += f / 2;
            odds += f % 2;
        }
        int ans = 0;
        for (int len : lens) {
            int need = len / 2;
            if (pairs < need) break;
            pairs -= need;
            if (len % 2) {
                if (odds == 0) {
                    if (pairs == 0) break;
                    pairs--;
                } else {
                    odds--;
                }
            }
            ans++;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

func maxPalindromesAfterOperations(words []string) int {
    lens := []int{}
    freq := make([]int, 26)
    for _, w := range words {
        lens = append(lens, len(w))
        for _, c := range w {
            freq[c-'a']++
        }
    }
    sort.Ints(lens)
    pairs, odds := 0, 0
    for _, f := range freq {
        pairs += f / 2
        odds += f % 2
    }
    ans := 0
    for _, l := range lens {
        need := l / 2
        if pairs < need {
            break
        }
        pairs -= need
        if l%2 == 1 {
            if odds == 0 {
                if pairs == 0 {
                    break
                }
                pairs--
            } else {
                odds--
            }
        }
        ans++
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
    public int maxPalindromesAfterOperations(String[] words) {
        int n = words.length;
        int[] lens = new int[n];
        int[] freq = new int[26];
        for (int i = 0; i < n; i++) {
            lens[i] = words[i].length();
            for (char c : words[i].toCharArray()) freq[c - 'a']++;
        }
        Arrays.sort(lens);
        int pairs = 0, odds = 0, ans = 0;
        for (int f : freq) {
            pairs += f / 2;
            odds += f % 2;
        }
        for (int len : lens) {
            int need = len / 2;
            if (pairs < need) break;
            pairs -= need;
            if (len % 2 == 1) {
                if (odds == 0) {
                    if (pairs == 0) break;
                    pairs--;
                } else {
                    odds--;
                }
            }
            ans++;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    fun maxPalindromesAfterOperations(words: Array<String>): Int {
        val lens = words.map { it.length }.sorted()
        val freq = IntArray(26)
        for (w in words) for (c in w) freq[c - 'a']++
        var pairs = freq.sumOf { it / 2 }
        var odds = freq.sumOf { it % 2 }
        var ans = 0
        for (len in lens) {
            val need = len / 2
            if (pairs < need) break
            pairs -= need
            if (len % 2 == 1) {
                if (odds == 0) {
                    if (pairs == 0) break
                    pairs--
                } else {
                    odds--
                }
            }
            ans++
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def maxPalindromesAfterOperations(self, words: list[str]) -> int:
        lens = sorted(len(w) for w in words)
        from collections import Counter
        freq = Counter()
        for w in words:
            freq.update(w)
        pairs = sum(v // 2 for v in freq.values())
        odds = sum(v % 2 for v in freq.values())
        ans = 0
        for l in lens:
            need = l // 2
            if pairs < need:
                break
            pairs -= need
            if l % 2:
                if odds == 0:
                    if pairs == 0:
                        break
                    pairs -= 1
                else:
                    odds -= 1
            ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

impl Solution {
    pub fn max_palindromes_after_operations(words: Vec<String>) -> i32 {
        let mut lens: Vec<usize> = words.iter().map(|w| w.len()).collect();
        lens.sort();
        let mut freq = [0; 26];
        for w in &words {
            for c in w.chars() {
                freq[c as usize - 'a' as usize] += 1;
            }
        }
        let mut pairs = freq.iter().map(|&f| f / 2).sum::<usize>();
        let mut odds = freq.iter().map(|&f| f % 2).sum::<usize>();
        let mut ans = 0;
        for &len in &lens {
            let need = len / 2;
            if pairs < need { break; }
            pairs -= need;
            if len % 2 == 1 {
                if odds == 0 {
                    if pairs == 0 { break; }
                    pairs -= 1;
                } else {
                    odds -= 1;
                }
            }
            ans += 1;
        }
        ans as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    maxPalindromesAfterOperations(words: string[]): number {
        const lens = words.map(w => w.length).sort((a, b) => a - b);
        const freq = new Array(26).fill(0);
        for (const w of words) for (const c of w) freq[c.charCodeAt(0) - 97]++;
        let pairs = freq.reduce((a, b) => a + Math.floor(b / 2), 0);
        let odds = freq.reduce((a, b) => a + (b % 2), 0);
        let ans = 0;
        for (const len of lens) {
            const need = Math.floor(len / 2);
            if (pairs < need) break;
            pairs -= need;
            if (len % 2 === 1) {
                if (odds === 0) {
                    if