Solution: Longest Palindrome

Statement#

Given a string s that contains only letters, return the length of the longest palindrome that may be composed using those letters.

Note: Letters are case-sensitive. For example, “Aa” is not considered a palindrome here.

Constraints:

• $1 \leq$ s.length $\leq 2000$

• s consists of lowercase and/or uppercase English letters only.

Solution#

In palindromes of even length, all the characters appear in pairs, while in palindromes of odd length, all the characters other than the middle one appear in pairs. In either case, to maintain the required symmetry, the paired characters must appear at the same distance on either side of the center of the string. For example, in “madam” and “racecar,” you can notice the arrangement of pairs of characters with a single unique character in the middle. We can exploit this property of palindromes to figure out which string is a valid palindrome and which isn’t. Further, extending this logic, we can even determine whether a rearrangement of a string exists that is a valid palindrome.

Now, to find the length of the longest palindrome in the given string, we need to find the maximum number of pairs of characters in the string, plus a unique character that will go in the middle of the palindrome (in the case of odd-length palindromes). We can use a hash map to store the characters as keys and their frequencies as values. Next, we’ll use the frequencies in our hash map to calculate the length of the palindrome.

Calculating the length of the palindrome:

For any given string, we can first make pairs of characters, which will be added to the result. This count of pairs can be calculated by halving the frequency of each character. Once the pairs are calculated, we have to multiply that count by $2$ to find the total number of characters that can be used to make the palindrome.

Let’s have a look at the following worked example to see how we calculate the contribution of one character, "a", to the overall length of the longest palindrome that may be formed from the given string:

Adjusting for odd-length palindromes:

After the loop, we’ll check whether the calculated length is less than the length of the original input string. If it is, it means that at least one character can be added as the center of the palindrome (an odd-length palindrome). In this case, we’ll increment the length by $1$ and return the result.

Let’s have a look at the code for the algorithm we just discussed:

Time complexity#

The time complexity of the solution above is $O(n)$, where $n$ is the length of the given input string.

Space complexity#

The space complexity of this solution is $O(n)$, which is the space occupied by the hash map.