3035. Maximum Palindromes After Operations
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.
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.
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, andmask
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 characterc
using the XOR operation (^
). This is done by shifting1
to the left(ord(c) - ord('a'))
times, effectively creating a bitmask where each bit represents one of the 26 lowercase letters.
- Update the
- Add the length of the current word to
-
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 numbermask
. -
Update
s
by subtracting the quantitymask.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 sortedwords
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
froms
. This represents the largest even number that is not greater thanlen(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 wordw
.
- 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
-
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 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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
andmask
. Here,s = 0
andmask = 0
. -
Iterate through each word in
words
to updates
andmask
.- For "abc":
s
becomes3
.mask
is updated for each character:mask = (mask ^ (1 << (ord(c) - ord('a'))))
forc
in "abc".- At the end,
mask
indicates odd counts for 'a', 'b', and 'c'.
- For "car":
s
becomes6
.- 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
becomes9
.- Update
mask
for 'a' and 'd'. - 'a' is now odd again, 'd' has an odd count, 'b' and 'c' remain odd, 'r' stays odd.
- For "abc":
-
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 areO(1)
. So, forn
words of average lengthk
, this part isO(nk)
. -
mask.bit_count()
computes the number of set bits inmask
. This operation is done once and isO(1)
. -
words.sort(key=len)
sorts the words based on their length. Python's sorting algorithm, Timsort, has a time complexity ofO(n log n)
wheren
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, consumingO(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 bywords
. Even if it does, it would at most consumeO(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.
Which data structure is used to implement priority queue?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!