Scale Engineer

Maximum Palindromes After Operations

Med
#2703Time: 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.2 companies
Patterns
GreedyCounting
Algorithms
Sorting
Data structures
ArrayHash TableString
Companies
GrammarlyMathWorks

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

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

Walkthrough

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.

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);    }}

Complexity

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.

Trade-offs

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.

Solutions

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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem