# Maximum Palindromes After Operations
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-palindromes-after-operations)
Canonical: https://scaleengineer.com/dsa/problems/maximum-palindromes-after-operations
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table, String
**Companies:** [Grammarly](https://scaleengineer.com/companies/grammarly), [MathWorks](https://scaleengineer.com/companies/mathworks)
---
## 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 the **maximum** number of palindromes_ `words` _can contain, after performing some operations._

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

**Example 1:**

**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:**

**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:**

**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.

# Approaches
## Brute-Force Backtracking
This approach models the problem as a series of choices. For each word, we can either choose to form a palindrome with it or skip it. This creates a binary decision tree. By exploring all possible paths in this tree using recursion (a backtracking method), we can find the combination of choices that yields the maximum number of palindromes. This method exhaustively checks every subset of words.
**Time:** O(2^N), where N is the number of words. In the worst case, we explore two branches for each word, leading to an exponential number of calls. · **Space:** O(N), where N is the number of words. This space is used by the recursion stack.
**Pros:** Conceptually straightforward, as it directly translates the problem's choices into code.; Guaranteed to find the correct answer, albeit very slowly.
**Cons:** Extremely inefficient due to its exponential time complexity.; Infeasible for the given constraints as it will lead to a 'Time Limit Exceeded' error.; Redundantly re-computes solutions for the same subproblems.
### Explanation
The brute-force backtracking approach systematically explores every possible subset of words that could be turned into palindromes. First, we pre-calculate the total number of available character pairs by counting all characters across all words. Then, we define a recursive function, say `solve(index, remaining_pairs)`, which represents the maximum number of palindromes we can form from the words starting at `index` with a given number of `remaining_pairs`.

For each word at `index`, the function makes two decisions:
1.  **Skip:** Don't make the current word a palindrome. We move to the next word (`index + 1`) with the same number of `remaining_pairs`.
2.  **Take:** Try to make the current word a palindrome. This is only possible if we have enough pairs for it. If so, we add 1 to our count and move to the next word with the `remaining_pairs` reduced by the amount used.

The function returns the maximum result from these two choices. The base case for the recursion is when we have considered all words (`index` reaches the end of the list), at which point we can't form any more palindromes, so we return 0.

```java
class Solution {
    private int[] lengths;

    public int maxPalindromesAfterOperations(String[] words) {
        int[] counts = new int[26];
        this.lengths = new int[words.length];
        int i = 0;
        for (String word : words) {
            lengths[i++] = word.length();
            for (char c : word.toCharArray()) {
                counts[c - 'a']++;
            }
        }

        int totalPairs = 0;
        for (int count : counts) {
            totalPairs += count / 2;
        }

        return solve(0, totalPairs);
    }

    private int solve(int index, int pairsLeft) {
        if (index == lengths.length) {
            return 0;
        }

        // Option 1: Skip this word
        int resSkip = solve(index + 1, pairsLeft);

        // Option 2: Take this word if possible
        int pairsNeeded = lengths[index] / 2;
        int resTake = 0; // Cannot take by default
        if (pairsLeft >= pairsNeeded) {
            resTake = 1 + solve(index + 1, pairsLeft - pairsNeeded);
        }

        return Math.max(resSkip, resTake);
    }
}
```
### Algorithm
1. Calculate the total number of available character pairs (`total_pairs`) by counting character frequencies across all words.
2. Create a list of word lengths.
3. Define a recursive function, `solve(index, pairs_left)`, that computes the maximum palindromes from `words[index...]` with `pairs_left` available.
4. In `solve(index, pairs_left)`:
   - Base Case: If `index` is out of bounds, return 0.
   - Choice 1 (Skip Word): Recursively call `solve(index + 1, pairs_left)`.
   - Choice 2 (Take Word): If `pairs_left` is sufficient for `words[index]` (i.e., `pairs_left >= lengths[index] / 2`), recursively call `1 + solve(index + 1, pairs_left - lengths[index] / 2)`.
   - Return the maximum of the results from the possible choices.
5. The initial call is `solve(0, total_pairs)`.

## Dynamic Programming (0/1 Knapsack)
This approach improves upon the brute-force method by using dynamic programming with memoization. The problem can be identified as a variation of the 0/1 Knapsack problem. The 'knapsack' has a capacity equal to the total available character pairs. Each word is an 'item' with a 'weight' equal to the number of pairs it requires (`length / 2`) and a 'value' of 1. The goal is to maximize the total value (number of words) without exceeding the knapsack's capacity. Memoization avoids re-computing results for the same state (`index`, `pairs_left`), drastically reducing the number of calculations.
**Time:** O(N * P), where N is the number of words and P is the total number of available pairs. Each state `(index, pairsLeft)` is computed once. · **Space:** O(N * P), where N is the number of words and P is the total number of pairs. This is for the memoization table.
**Pros:** Significantly more efficient than brute-force.; Guaranteed to find the optimal solution by exploring the problem space systematically.
**Cons:** The space complexity is O(N * P), which can be large if the total number of pairs `P` is high.; The time complexity, while better than exponential, is still pseudo-polynomial and may be too slow if `P` is very large.
### Explanation
The key observation is that the brute-force backtracking approach solves the same subproblems multiple times. For example, the result for `solve(5, 10)` might be needed through different paths of choices for the first four words. We can cache the results to avoid this redundant work.

A 2D array, `memo`, can be used for this, where `memo[i][j]` stores the result for `solve(i, j)`. When the function is called, it first checks the memoization table. If a result exists, it's returned instantly. Otherwise, the result is computed as in the backtracking approach, and then stored in the table before being returned. This ensures that each unique subproblem `(index, pairs_left)` is solved only once.

```java
class Solution {
    private int[] lengths;
    private Integer[][] memo;

    public int maxPalindromesAfterOperations(String[] words) {
        int[] counts = new int[26];
        this.lengths = new int[words.length];
        int i = 0;
        for (String word : words) {
            lengths[i++] = word.length();
            for (char c : word.toCharArray()) {
                counts[c - 'a']++;
            }
        }

        int totalPairs = 0;
        for (int count : counts) {
            totalPairs += count / 2;
        }
        
        memo = new Integer[words.length][totalPairs + 1];
        return solve(0, totalPairs);
    }

    private int solve(int index, int pairsLeft) {
        if (index == lengths.length) {
            return 0;
        }
        if (memo[index][pairsLeft] != null) {
            return memo[index][pairsLeft];
        }

        // Option 1: Skip this word
        int resSkip = solve(index + 1, pairsLeft);

        // Option 2: Take this word if possible
        int pairsNeeded = lengths[index] / 2;
        int resTake = 0;
        if (pairsLeft >= pairsNeeded) {
            resTake = 1 + solve(index + 1, pairsLeft - pairsNeeded);
        }

        return memo[index][pairsLeft] = Math.max(resSkip, resTake);
    }
}
```
### Algorithm
1. Calculate `total_pairs` and a list of `lengths` as in the previous approach.
2. Create a 2D memoization table, `memo[N][total_pairs + 1]`, to store the results of subproblems. Initialize it with a sentinel value (e.g., `null` or -1).
3. Use the same recursive function `solve(index, pairs_left)`.
4. Before any computation within `solve`, check if `memo[index][pairs_left]` already contains a result. If so, return it immediately.
5. After computing the result for `(index, pairs_left)`, store it in `memo[index][pairs_left]` before returning.

## Optimal Greedy Approach
The most efficient solution is a greedy one. The problem is a special case of the 0/1 knapsack problem where all items have a value of 1. In this scenario, the optimal strategy to maximize the number of items is to always pick the items with the smallest 'weight' first. Here, the 'items' are the words, and their 'weight' is the number of character pairs they require (`length / 2`). By sorting the words by length (and thus by pairs required) and greedily fulfilling their needs, we can find the maximum number of palindromes efficiently.
**Time:** O(M + N log N), where M is the total number of characters in all words (for frequency counting) and N is the number of words (for sorting). This is the most efficient solution. · **Space:** O(N) to store the word lengths for sorting. The frequency map requires O(1) space.
**Pros:** Highly efficient with a polynomial time complexity, much better than DP.; Simple to implement and understand once the greedy logic is clear.; Low space complexity.
**Cons:** The correctness of the greedy choice is not immediately obvious and relies on an understanding of the underlying resource allocation problem.
### Explanation
This approach leverages a key insight: to maximize the number of palindromes, we should prioritize forming palindromes from shorter words because they consume the fewest resources (character pairs). The ability to swap any character means we only need to care about the total count of pairs, not which specific characters form them.

The algorithm is as follows: First, we compute the total number of character pairs available from the entire character pool of all words. Second, we get the lengths of all words and sort them in non-decreasing order. Finally, we iterate through the sorted lengths, and for each length, we check if we have enough pairs. If we do, we 'form' the palindrome, increment our count, and deduct the used pairs from our total. If we don't, we stop, as we won't be able to form any longer palindromes either.

This greedy strategy is optimal because by satisfying the cheapest requests first, we maximize the number of requests we can satisfy in total.

```java
import java.util.Arrays;

class Solution {
    public int maxPalindromesAfterOperations(String[] words) {
        int[] counts = new int[26];
        int[] lengths = new int[words.length];
        int i = 0;
        for (String word : words) {
            lengths[i++] = word.length();
            for (char c : word.toCharArray()) {
                counts[c - 'a']++;
            }
        }

        int totalPairs = 0;
        for (int count : counts) {
            totalPairs += count / 2;
        }

        Arrays.sort(lengths);

        int palindromes = 0;
        for (int len : lengths) {
            int pairsNeeded = len / 2;
            if (totalPairs >= pairsNeeded) {
                totalPairs -= pairsNeeded;
                palindromes++;
            } else {
                break;
            }
        }
        return palindromes;
    }
}
```
### Algorithm
1. Count the frequency of all characters across all words.
2. From the frequencies, calculate the `total_pairs` available. For a character with frequency `f`, it contributes `f / 2` pairs.
3. Create a list of the lengths of all words.
4. Sort the list of lengths in ascending order.
5. Initialize a palindrome counter to 0.
6. Iterate through the sorted lengths:
   - For each length `L`, calculate the pairs needed: `pairs_needed = L / 2`.
   - If `total_pairs >= pairs_needed`, it's possible to form this palindrome. Increment the counter and decrease `total_pairs` by `pairs_needed`.
   - If `total_pairs < pairs_needed`, we don't have enough pairs. Since the lengths are sorted, we cannot satisfy any subsequent, longer words either. Break the loop.
7. Return the palindrome counter.

# Solutions
### Java

```java
class Solution {
public
  int maxPalindromesAfterOperations(String[] words) {
    int s = 0, mask = 0;
    for (var w : words) {
      s += w.length();
      for (var c : w.toCharArray()) {
        mask ^= 1 << (c - 'a');
      }
    }
    s -= Integer.bitCount(mask);
    Arrays.sort(words, (a, b)->a.length() - b.length());
    int ans = 0;
    for (var w : words) {
      s -= w.length() / 2 * 2;
      if (s < 0) {
        break;
      }
      ++ans;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxPalindromesAfterOperations(vector<string> &words) {
    int s = 0, mask = 0;
    for (const auto &w : words) {
      s += w.length();
      for (char c : w) {
        mask ^= 1 << (c - 'a');
      }
    }
    s -= __builtin_popcount(mask);
    sort(words.begin(), words.end(), [](const string &a, const string &b) {
      return a.length() < b.length();
    });
    int ans = 0;
    for (const auto &w : words) {
      s -= w.length() / 2 * 2;
      if (s < 0) {
        break;
      }
      ++ans;
    }
    return ans;
  }
};

```

### Python

```python
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

```