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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Palindrome

Number: 409

Difficulty: Easy

Paid? No

Companies: Google, Amazon, Bloomberg, Meta, Oracle, Walmart Labs

Problem Description

Given a string s consisting of lowercase or uppercase English letters, determine the length of the longest palindrome that can be built with those letters. Letters are case sensitive.

Key Insights

  • Count the frequency of each character.
  • For each character, you can use pairs (even count or odd count minus one) to form the palindrome.
  • If any character has an odd frequency, you can add one extra character as the center of the palindrome.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1) since the frequency counter will have at most 52 keys (considering both uppercase and lowercase letters).

Solution

The solution uses a hash table to count the frequency of each character. For every character, the maximum number of characters that can be used in a palindrome is determined by taking the largest even number that is less than or equal to its frequency (which is frequency - (frequency % 2)). If there exists any character with an odd frequency, one of these can be used as the center of the palindrome, adding an extra character to the total length. This greedy approach efficiently computes the length of the largest possible palindrome from the available characters.

Code Solutions

# Python solution for the Longest Palindrome problem

def longestPalindrome(s: str) -> int:
    # Create a dictionary to store the frequency of each character
    char_counts = {}
    for char in s:
        # Increment the count for the character
        char_counts[char] = char_counts.get(char, 0) + 1
        
    # Variable to store the length of the palindrome
    palindrome_length = 0
    # Flag to indicate whether we can add one more character in the middle for an odd count
    center_added = False
    
    # Iterate through the character counts
    for count in char_counts.values():
        # Add the largest even number from count to palindrome_length
        palindrome_length += (count // 2) * 2
        # If count is odd and we haven't added the center character yet
        if count % 2 == 1 and not center_added:
            palindrome_length += 1
            center_added = True
            
    return palindrome_length

# Example usage:
print(longestPalindrome("abccccdd"))
← Back to All Questions