Longest palindrome from equal-length words

You are given a list of words. Every word has the same length k and uses lowercase letters. The list can contain duplicates.

Pick some of the words (possibly none) and join them in any order to form a palindrome. Each entry in the list can be used at most once, so a word can appear as many times as it occurs in the list, and no more.

Implement:

def longest_palindrome_length(words: list[str]) -> int: ...
def build_longest_palindrome(words: list[str]) -> str: ...

• longest_palindrome_length returns the length of the longest palindrome you can build, or 0 if you cannot build one.
• build_longest_palindrome returns one such palindrome, or "".

Constraints

• 0 <= len(words) <= 10^5
• 1 <= k <= 10, and all words have length k

Example 1

words = ["ab", "ba", "cc", "cc", "cc"]
longest_palindrome_length(words) -> 10
build_longest_palindrome(words)  -> "abccccccba"

"ab" and "ba" mirror each other, two "cc" form another mirror pair, and the third "cc" goes in the middle.

Example 2

words = ["abc", "cba", "bab", "xyx"]
longest_palindrome_length(words) -> 9

For example "abcbabcba". Only one of "bab" and "xyx" can be in the middle.

Reconstructed from the reported question; details may differ from what interviewers ask.