We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Palindrome

Difficulty: Easy

Problem Description

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.

Key Insights

  • A palindrome reads the same forwards and backwards.
  • To form a palindrome, characters must be paired, with at most one character allowed to be unpaired (which can sit in the middle).
  • Count the occurrences of each character in the string.
  • The maximum length of the palindrome can be determined by summing the lengths of pairs of characters, and adding one if there's at least one unpaired character.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s, as we need to iterate through the string to count character frequencies.

Space Complexity: O(1), since the maximum number of unique characters is limited (52 for English letters).

Solution

To solve the problem, we can use a hash table (or a simple array) to count the occurrences of each character in the string. After counting, we iterate through the counts to calculate the total length of the palindrome. For each character count, we can add the largest even number possible (which forms pairs) to the total length, and if there is at least one odd count, we can add one more to account for the central character in the palindrome.

Code Solutions

def longestPalindrome(s: str) -> int:
    char_count = {}
    
    # Count the occurrences of each character
    for char in s:
        char_count[char] = char_count.get(char, 0) + 1
    
    length = 0
    odd_found = False
    
    # Calculate the length of the longest palindrome
    for count in char_count.values():
        if count % 2 == 0:
            length += count  # Add all pairs
        else:
            length += count - 1  # Add the maximum even part
            odd_found = True  # Mark that we found an odd count
    
    # If there's at least one odd count, we can add one more character
    if odd_found:
        length += 1
    
    return length
← Back to All Questions