algoadvance

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

Letters are case-sensitive, for example, “Aa” is not considered a palindrome.

Clarifying Questions

  1. Palindrome Definition: A palindrome is a string that reads the same forward and backward, e.g., “racecar”.
  2. Input Constraints:
    • The input string will have a length between 1 and 2000.
    • The string consists only of uppercase and lowercase English letters.
  3. Do we need to return the longest palindromic substring or its length?
    • We need to return the length of the longest palindromes that can be built with the given characters.

Strategy

  1. Character Frequency Counting:
    • Use a dictionary or a collections.Counter to count the frequency of each character in the string.
  2. Pair Counting:
    • Initialize a variable to keep track of the length of the longest palindrome.
    • Iterate through the frequency counts and add the largest even number less than or equal to that count (this is because pairs of characters can contribute to a palindrome).
  3. Odd Frequency Handling:
    • If there is at least one character with an odd frequency count, we can include one of those characters in the middle of the palindrome to maximize its length.

Code

from collections import Counter

def longestPalindrome(s: str) -> int:
    freq = Counter(s)
    length = 0
    odd_found = False
    
    for count in freq.values():
        if count % 2 == 0:
            length += count
        else:
            length += count - 1
            odd_found = True
    
    if odd_found:
        length += 1
    
    return length

# Example usage
s = "abccccdd"
print(longestPalindrome(s))  # Expected output: 7

Explanation:

  1. Count Frequencies:
    • Use Counter(s) to get the frequency of each character.
  2. Sum Even Counts:
    • If a count is even, add it directly to length since all of these characters can be paired up perfectly.
  3. Handle Odd Counts:
    • If a count is odd, add the largest even part (i.e., count - 1) to length to maximize the number of pairs.
    • Keep track of any odd count using the odd_found flag.
  4. Include One Odd:
    • If there was any odd count, add 1 to length to account for one character that can sit in the middle of the palindrome.

Time Complexity

Try our interview co-pilot at AlgoAdvance.com