Problem Statement:
Given a string, determine the length of the longest palindrome that can be constructed using the characters from the string. Return the maximum possible length of the palindromic string.
Examples:
-
- Input: "applepie"
- Expected Output: 5
- Justification: The longest palindrome that can be constructed from the string is "pepep", which has a length of 5. There are other palindromes too but they all will be of length 5.
-
- Input: "aabbcc"
- Expected Output: 6
- Justification: We can form the palindrome "abccba" using the characters from the string, which has a length of 6.
-
- Input: "bananas"
- Expected Output: 5
- Justification: The longest palindrome that can be constructed from the string is "anana", which has a length of 5.
Constraints:
1 <= s.length <= 2000sconsists of lowercase and/or uppercase English letters only.
Why this is a Hash Maps problem
| What the question says | The signal it matches |
|---|---|
| "the length of the longest palindrome that can be constructed using the characters from the string" | the characters may be rearranged, so this is a collection rather than a sequence |
| "You don't need to return the palindrome itself, just its maximum possible length" | only the counts matter, never the arrangement |
| trying to build palindromes and measuring them | the brute force explores arrangements that the counts make unnecessary |
Tallying the letters and reasoning about the tally is the count, then reason about the counts variant.
The closest alternative. The word palindrome suggests the Palindromic Subsequence problems, which are covered in Grokking the Coding Interview rather than in this course. None of that applies here. Those problems fix the order of the string.
Here the letters can be rearranged freely, which reduces the question to arithmetic. Every letter contributes its count rounded down to an even number. Add one more if any letter was left with an odd count.
Solution
To solve this problem, we can use a hashmap to keep track of the frequency of each character in the string. The idea is to use pairs of characters to form the palindrome. For example, if a character appears an even number of times, we can use all of them in the palindrome. If a character appears an odd number of times, we can use all except one of them in the palindrome. Additionally, if there's any character that appears an odd number of times, we can use one of them as the center of the palindrome.
-
Initialization: Start by initializing a hashmap to keep track of the characters and their frequencies.
-
Character Counting: Iterate through the string and populate the hashmap with the frequency of each character.
-
Palindrome Length Calculation: For each character in the hashmap, if it appears an even number of times, add its count to the palindrome length. If it appears an odd number of times, add its count minus one to the palindrome length. Also, set a flag indicating that there's a character available for the center of the palindrome.
-
Final Adjustment: If the center flag is set, add one to the palindrome length.
Algorithm Walkthrough
One walk over the string fills the map: b appears 1 time, a appears 3 times, n appears 2 times, s appears 1 time. From here the string itself is never looked at again. Only the counts matter, because a palindrome is built from PAIRS and a pair can be taken from anywhere.
1 of 8
Code
Here is the code for this algorithm:
Time Complexity:
-
Iterating through the string: We iterate through the entire string once to count the frequency of each character. This operation takes O(n) time, where n is the length of the string.
-
Iterating through the hashmap: After counting the frequencies, we iterate through the hashmap to determine how many characters can be used to form the palindrome. The constraints allow lowercase and uppercase English letters, so the map can hold at most 52 entries. In the worst case this is O(52), which is a constant, and it is the same bound the space analysis below uses. However, in general terms, if we consider any possible character (not just English alphabet), this would be O(k), where k is the number of unique characters in the string.
Combining the two steps, the overall time complexity is O(n) + O(k) = O(n) as k<= n .
Space Complexity:
Hashmap for character frequencies: The space taken by the hashmap is proportional to the number of unique characters in the string. In the worst case, this would be O(52) here, since the constraints allow both lowercase and uppercase English letters, which is a constant. However, in general terms, if we consider any possible character (not just English letters), this would be O(k), where k is the number of unique characters in the string.
Thus, the space complexity of the algorithm is O(1).
.....
.....
.....