Longest Palindrome easy

Problem Statement

Given a string s which consists of lowercase or uppercase letters, find 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 here.

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.

Steps

1. Character Counting: Create a dictionary (or a similar data structure) to count the occurrences of each character in the input string s.

2. Odd and Even Counts: Iterate through the character counts. Separate the counts into two groups: those that are even and those that are odd.

3. Calculate Length: The length of the longest palindrome is calculated as follows:

   • Sum of all even counts (each even count contributes its full value to the palindrome).
   • Add 1 if there is at least one odd count (this accounts for the middle character of the palindrome if the total number of characters is odd).

Explanation

The key idea is that a palindrome can be built by pairing up characters. Even counts contribute their full value because we can pair all occurrences. Odd counts contribute all but one, and the single leftover character can be placed in the middle of the palindrome.

For example, in "abccccdd", we have:

• 'a': 1 (odd)
• 'b': 1 (odd)
• 'c': 4 (even)
• 'd': 2 (even)

Even counts ('c' and 'd') contribute 4 + 2 = 6 to the palindrome length. One of the odd counts ('a' or 'b') can form the middle of the palindrome, adding 1 to the length. Thus the total length is 6 + 1 = 7.

Code

from collections import Counter

def longestPalindrome(s):
    """
    Finds the length of the longest palindrome that can be built from a string.

    Args:
      s: The input string.

    Returns:
      The length of the longest palindrome.
    """
    char_counts = Counter(s)  #Efficient way to count character occurrences
    even_counts_sum = 0
    odd_count_exists = False

    for count in char_counts.values():
        if count % 2 == 0:
            even_counts_sum += count
        else:
            even_counts_sum += count - 1  #Use all but one of odd counts
            odd_count_exists = True

    return even_counts_sum + int(odd_count_exists) #Add 1 if there's an odd count

Complexity

• Time Complexity: O(n), where n is the length of the string. This is dominated by the character counting step using Counter.
• Space Complexity: O(1) in the average case, because the number of unique characters in the alphabet is constant (52 for uppercase and lowercase English letters). In the worst-case scenario (all unique characters), it would be O(n). However, for this specific problem, O(1) is a more accurate reflection due to the constraint of the input.