{x}
blog image

Longest Palindrome

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.

Letters are case sensitive, for example, "Aa" is not considered a palindrome.

 

Example 1:

Input: s = "abccccdd"
Output: 7
Explanation: One longest palindrome that can be built is "dccaccd", whose length is 7.

Example 2:

Input: s = "a"
Output: 1
Explanation: The longest palindrome that can be built is "a", whose length is 1.

 

Constraints:

  • 1 <= s.length <= 2000
  • s consists of lowercase and/or uppercase English letters only.

Solution Explanation for Longest Palindrome

The problem asks to find the length of the longest palindrome that can be built from the characters of a given string. A palindrome is a sequence that reads the same backward as forward.

Both solutions presented leverage the fact that a palindrome can have at most one character with an odd count. All other characters must appear an even number of times.

Solution 1: Counting

This solution uses a counting approach:

  1. Character Counting: It first counts the occurrences of each character in the input string s using a hash map (or a simple array if the character set is known and limited, as in this case, using ASCII characters).

  2. Even Count Contribution: It iterates through the counts of each character. For each character, it calculates the maximum number of even occurrences ( v // 2 * 2 in Python, v / 2 * 2 in other languages). This is because each even pair of characters contributes to the palindrome. These even contributions are summed up to ans.

  3. Odd Count Handling: If the total length ans is less than the length of the original string s, it means there's at least one character with an odd count. We can include one such character in the middle of the palindrome, incrementing ans by 1.

  4. Return Length: Finally, it returns ans, which represents the length of the longest palindrome.

Time Complexity: O(n + k), where n is the length of the string and k is the size of the character set (128 for ASCII). The counting phase takes O(n), and iterating through the counts takes O(k). In practice, it's effectively O(n) because k is a constant.

Space Complexity: O(k) to store character counts. Again, this is constant space complexity in practice.

Solution 2: Bit Manipulation and Counting

This solution employs bit manipulation for a more concise approach:

  1. Odd/Even Tracking: It uses a hash map (odd in the code) to track whether the count of each character is odd (1) or even (0). It also uses a counter cnt to keep track of the number of characters with odd counts.

  2. XOR for Odd/Even Check: The core idea is to use XOR (^= operator). XORing a number with 1 toggles its least significant bit. Thus, odd[c] ^= 1 flips the value between 0 and 1, representing even and odd counts, respectively.

  3. Count Adjustment: If odd[c] changes from 0 to 1 (becomes odd), cnt is incremented. If it changes from 1 to 0 (becomes even), cnt is decremented.

  4. Palindrome Length Calculation: If cnt is greater than 0, it means there are characters with odd counts. The length of the longest palindrome is then n - cnt + 1 (subtract the excess odd characters and add one for the central character). Otherwise, all character counts are even, and the length is simply n.

Time Complexity: O(n) – The loop iterates through the string once.

Space Complexity: O(k) – Similar to solution 1, space used is proportional to the character set size.

In Summary: Both solutions achieve the same result. Solution 1 is arguably easier to understand, while Solution 2 is more concise and potentially slightly faster due to avoiding the division operation. The choice depends on the preference for readability versus conciseness.