3035. Maximum Palindromes After Operations

MediumGreedyArrayHash TableStringCountingSorting

Problem Description

The given problem presents a scenario where you have an array of words words indexed starting from 0. The goal is to transform some of these words into palindromes. A palindrome is a word that reads the same backward as forward, like "radar" or "level".

We're provided with a specific operation that can be performed an unlimited number of times to help create palindromes. In each operation, you're allowed to choose two characters from anywhere in the array (the same word or from different words) and swap them.

The task is to find out the maximum number of palindromes that can be obtained in the array after performing any number of the described operations.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

When trying to form palindromes, it's crucial to note that a palindrome can either have all characters with even counts and at most one character with an odd count. This odd-count character, if it exists, will sit right in the middle of the palindrome.

This implies that in order to maximize the number of palindromes, we need to look at the entire set of characters across all words and ensure that we use as many even counts of characters as possible, allowing for a single odd-count character per palindrome when needed.

With this understanding, we can move through the array of words to calculate the total length of all words, s, and a bitmask, mask, that tracks the count of each character. If a bit in mask is set, it indicates an odd count for that character across all words. The bit count of mask then gives us the total number of odd-count characters.

By subtracting the bit count of mask from s, we're effectively pairing up as many letters as possible to create even counts, leaving us with the odd counts, if any.

Then, we sort the words by length to start attempting palindrome creation with the shortest words first. As we iterate, if there's not enough length left in s to form a palindrome (that is, we need an even number of characters), we break and return the current count of palindromes possible, ans.

The solution approach makes clever use of bit manipulation to efficiently count odd character occurrences and quickly determine if those characters can be paired up or need to be placed in the middle of a palindrome. It prioritizes creating palindromes out of shorter words first because longer words have a higher 'cost' in term of character count and could better be used by breaking them down to form multiple smaller palindromes.

Learn more about Greedy and Sorting patterns.

Solution Approach

The solution employs a bit manipulation strategy to efficiently track character frequencies from all the words combined, as well as sorting and simple arithmetic to determine the maximum number of palindromes.

Here's a breakdown of the algorithm:

Initialize two variables: s to accumulate the total length of all words, and mask as a bitmask to keep track of the odd counts of characters.
Iterate through each word in words:
- Add the length of the current word to s.
- Iterate through each character c in the word:
  - Update the mask by toggling the bit corresponding to the character c using the XOR operation (^). This is done by shifting 1 to the left (ord(c) - ord('a')) times, effectively creating a bitmask where each bit represents one of the 26 lowercase letters.
Calculate the number of odd-count characters by finding the bit count of mask. mask.bit_count() is a built-in Python method that returns the number of set bits (1s) in the binary representation of the number mask.
Update s by subtracting the quantity mask.bit_count(), thus adjusting for the number of characters that can't be paired.
Sort words by the length of the word in ascending order to prioritize creating palindromes with shorter words.
Initialize an answer variable ans to 0, which will keep track of the number of palindromes formed.
Iterate through each word w in the sorted words list:
- Calculate the number of characters we can safely use to form palindromes from this word without breaking the possibility of forming palindromes from the remaining words. This is done by subtracting len(w) // 2 * 2 from s. This represents the largest even number that is not greater than len(w).
- If s becomes negative, it means we have run out of characters that can be paired, so we break out of the loop.
- Otherwise, we increment ans since we can form a palindrome from the current word w.
Finally, return ans, which now contains the maximum number of palindromes that can be formed.

This solution uses bit manipulation to efficiently handle character counts and arithmetic operations to manage palindrome formation. It sorts words as a preprocessing step to maximize the total number of palindromes formed by first using shorter words that require fewer character pairs.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with an example. Suppose we have the following array of words:

words = ["abc", "car", "ada"]

Following the steps described in the solution approach:

Initialize s and mask. Here, s = 0 and mask = 0.
Iterate through each word in words to update s and mask.
- For "abc":
  - s becomes 3.
  - mask is updated for each character: mask = (mask ^ (1 << (ord(c) - ord('a')))) for c in "abc".
  - At the end, mask indicates odd counts for 'a', 'b', and 'c'.
- For "car":
  - s becomes 6.
  - Update mask for 'c', 'a', and 'r'.
  - 'a' has even count now, 'b' and 'c' remain with odd count, and 'r' is added with odd count.
- For "ada":
  - s becomes 9.
  - Update mask for 'a' and 'd'.
  - 'a' is now odd again, 'd' has an odd count, 'b' and 'c' remain odd, 'r' stays odd.
Count the number of od

Solution Implementation

1class Solution:
2    def maxPalindromesAfterOperations(self, words: List[str]) -> int:
3        total_length = bitmask = 0
4      
5        # Iterate over each word to determine the total length
6        # and create a bitmask representing the characters
7        for word in words:
8            total_length += len(word)
9            for char in word:
10                bitmask ^= 1 << (ord(char) - ord('a'))
11      
12        # Reduce the total length by the number of unique chars
13        # to balance palindrome by removing extra occurrences
14        total_length -= bin(bitmask).count('1')
15      
16        # Sort words by length in ascending order
17        words.sort(key=len)
18      
19        max_palindromes = 0
20      
21        # Try to form as many palindromes as possible
22        for word in words:
23            if total_length < 0:
24                # If the total length is negative, break from the loop
25                break
26
27            # Deduct the even part of current word length since
28            # they can potentially be placed in the middle of a palindrome
29            total_length -= (len(word) // 2) * 2
30          
31            # Increment the count of max palindromes that can be formed
32            max_palindromes += 1
33      
34        return max_palindromes
35```
36
37Please note that using `List` requires an import from `typing` module in Python 3. To use the `List` annotation, add the following line at the beginning of the file:
38
39```python
40from typing import List
41

1class Solution {
2    public int maxPalindromesAfterOperations(String[] words) {
3        // Initialize the sum of string lengths and a bitmask to track character occurrences
4        int stringLengthSum = 0;
5        int characterMask = 0;
6
7        // Iterate through each word in the array
8        for (String word : words) {
9            // Add the length of the word to the total sum of string lengths
10            stringLengthSum += word.length();
11
12            // Toggle bits in the characterMask for each character in the word
13            for (char c : word.toCharArray()) {
14                characterMask ^= 1 << (c - 'a');
15            }
16        }
17
18        // Subtract the number of odd character counts from the sum to leave pairs for palindrome
19        stringLengthSum -= Integer.bitCount(characterMask);
20
21        // Sort the array of words by their lengths in ascending order
22        Arrays.sort(words, (a, b) -> a.length() - b.length());
23
24        // Initialize count of possible palindromes
25        int palindromeCount = 0;
26      
27        // Iterate through sorted words
28        for (String word : words) {
29            // Deduct twice the half length of the current word from the sum
30            stringLengthSum -= word.length() / 2 * 2;
31          
32            // If the remaining sum is negative, break out of the loop
33            if (stringLengthSum < 0) {
34                break;
35            }
36
37            // Increment counter for possible palindromes
38            ++palindromeCount;
39        }
40        // Return the count of possible palindromes after the operations
41        return palindromeCount;
42    }
43}
44

1#include <vector>
2#include <string>
3#include <algorithm>
4
5class Solution {
6public:
7    int maxPalindromesAfterOperations(std::vector<std::string>& words) {
8        int stringLengthSum = 0;  // Initialize the sum of word lengths to zero
9        int charMask = 0;         // Bitmask for tracking character occurrences
10
11        // Loop over each word and process characters
12        for (const auto& word : words) {
13            stringLengthSum += word.length();  // Add word's length to the total sum
14            // XOR bitmask for each character in the word to track even/odd occurrences
15            for (char c : word) {
16                charMask ^= 1 << (c - 'a');
17            }
18        }
19
20        // Subtract the number of characters with odd occurrences from the length sum
21        stringLengthSum -= __builtin_popcount(charMask);
22
23        // Sort the words by their lengths in ascending order
24        std::sort(words.begin(), words.end(), [](const std::string& a, const std::string& b) {
25            return a.length() < b.length();
26        });
27
28        int maxPalindromes = 0;  // Counter for maximum number of palindromes
29
30        // Loop through each word to calculate the maximum number of palindromes
31        for (const auto& word : words) {
32            // Reduce the total string length by the largest even length that can form a palindrome
33            stringLengthSum -= word.length() / 2 * 2; 
34            // If the sum of remaining lengths is negative, break out of the loop
35            if (stringLengthSum < 0) {
36                break;
37            }
38            ++maxPalindromes;  // Increment max palindromes as current word can form a palindrome
39        }
40
41        return maxPalindromes;  // Return the maximum number of palindromes
42    }
43};
44

1function maxPalindromesAfterOperations(words: string[]): number {
2    let totalLength: number = 0;  // Initialize a variable to hold the total length of all words
3    let bitMask: number = 0;      // Initialize a bit mask to track the occurrence of characters
4
5    // Iterate over the array of words
6    for (const word of words) {
7        totalLength += word.length;  // Add the length of the current word to totalLength
8        // Iterate over the characters in the current word
9        for (const character of word) {
10            // Toggle the bit in bitMask corresponding to the character
11            bitMask ^= 1 << (character.charCodeAt(0) - 'a'.charCodeAt(0));
12        }
13    }
14
15    // Subtract the count of set bits in bitMask from totalLength, since we can only form palindromes with
16    // an even count of each character, aside from possibly one character in the middle of a palindrome
17    totalLength -= (bitMask.toString(2).match(/1/g) || []).length;
18
19    // Sort the words array by the length of each word in ascending order
20    words.sort((a, b) => a.length - b.length);
21
22    let maxPalindromeCount: number = 0;  // Initialize the counter for the max number of palindromes possible
23
24    // Iterate over the sorted array of words
25    for (const word of words) {
26        const halfWordLength: number = Math.floor(word.length / 2) * 2;
27        totalLength -= halfWordLength;  // Reduce the totalLength by the even part of the current word's length
28
29        if (totalLength < 0) {
30            // If the totalLength becomes negative, we cannot form more palindromes, so we break the loop
31            break;
32        }
33        maxPalindromeCount++;  // Increment the count of possible palindromes
34    }
35
36    // Return the maximum number of palindromes that can be made after possible operations
37    return maxPalindromeCount;
38}
39

Time and Space Complexity

Time Complexity

The provided code performs several operations to determine the maximum number of words that can be converted to palindromes by removing some characters. The time complexity analysis is based on the following steps:

The first loop runs through each word in words, performing an XOR operation for each character to track the character frequencies as bits. The XOR and increment operations inside the loop are O(1). So, for n words of average length k, this part is O(nk).
mask.bit_count() computes the number of set bits in mask. This operation is done once and is O(1).
words.sort(key=len) sorts the words based on their length. Python's sorting algorithm, Timsort, has a time complexity of O(n log n) where n is the number of words.
The second loop iterates over the words again and performs a constant number of operations for each word, which gives us O(n).

The most time-consuming operation is the sorting, which is O(n log n) combined with the first loop (O(nk)), leading to an overall time complexity of O(nk + n log n).

Space Complexity

The space complexity analysis considers the memory usage of the algorithm, which includes the following aspects:

The mask is an integer that stores character frequency as bits, consuming O(1) space.
The sorted word list is in-place; hence it does not consume additional space, assuming the sort method in Python does not consume additional space beyond what is already used by words. Even if it does, it would at most consume O(n) space.
There are no additional data structures used that scale with the input size. Therefore, the space complexity remains constant, at O(1).

Combining the above points, the overall space complexity of the code is O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1

dp[i] = dp[i] + dp[i - 1]

dp[i] = (dp[i] + dp[j] + 1) for j in 0 to i

dp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don't know