palindrome.py

def maximal_palindrome(s: str) -> str:
    """
    Given a string of letters, find the maximum length possible palindrome

    Parameters
    ----------
    s : str
        input string of letters, e.g. "abaacc"

    Returns
    -------
    str
        maximum palindrome, e.g. "acaca"
    """

    result = []
    s = s.strip()
    unique_letters = ''.join(set(s))
    unique_letters_sorted = sorted(unique_letters)

    # create a dictionary of letter counts we have for each unique letter
    letter_count_dict = {}
    for letter in unique_letters:
        letter_count_dict[letter] = s.count(letter)

    # loop over the sorted list of letters
    for letter in unique_letters_sorted:
    # if we have more than one letter, add n/2 of those letters to result list
    # update letter count dict acordingly
        if letter_count_dict[letter] >= 2:
            equal_num_available = int(letter_count_dict[letter]/2)
            result.append(letter*equal_num_available)
            letter_count_dict[letter] -= 2*equal_num_available

    # add leftover smallest letter - to be added to the middle
    leftover_smallest = ""
    for letter in unique_letters_sorted:
        if letter_count_dict[letter] > 0:
            leftover_smallest = letter
            break

    # create final result, since we added n/2 of each unique letter above,
    # we can just reverse that list
    result = result + [leftover_smallest] + result[::-1]

    # convert to string and return
    return "".join(result)