Longest palindrome from equal-length words

Question: Longest palindrome from equal-length words

Companies: Microsoft, Meta

Difficulty: Medium

Problem statement

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.

Approach

Key observation. Every word has the same length k. In a palindrome made of m words, the reversed string is the same m words in reverse order, each reversed. Because the word boundaries line up (all words have length k), the word at position i must equal the reverse of the word at position m - 1 - i. So the palindrome is built from:

• mirror pairs: a word w on the left and reverse(w) on the right, and
• at most one center word, which must be a palindrome itself (it sits at position i = m - 1 - i).

Brute force. Try every subset and every order, and check each string. This is O(n! * n * k). It only helps to state the structure; nobody codes it.

Optimal: count and pair greedily.

1. Count each word with a hash map.
2. For a word w that is not a palindrome, let r = reverse(w). Visit each unordered pair {w, r} once. It gives min(count[w], count[r]) mirror pairs.
3. For a word w that is a palindrome, copies pair with each other: count[w] // 2 pairs. If count[w] is odd, one copy is left over and can be the center.
4. Length = 2 * pairs * k, plus k if any palindromic word has a leftover copy.

Why greedy is optimal. Pair groups do not compete. A word w can only be matched with reverse(w), so each group {w, reverse(w)} is independent, and in each group taking the maximum number of pairs is never worse. Only one center is allowed, and any leftover palindrome fills it with the same k characters, so it does not matter which one we choose.

Building the string. Put the left half in a fixed order (sorted, so the output is deterministic). Then add the center, then the left half reversed with each word reversed. That right half is exactly the reverse of the left half, so the result is a palindrome.

Invariants: every word used at most as many times as it appears; left and its mirror always have the same number of words; the center, if present, is a palindrome.

Code

from collections import Counter


def _is_pal(s: str) -> bool:
    return s == s[::-1]


def longest_palindrome_length(words: list[str]) -> int:
    """Length of the longest palindrome made by joining some words.

    All words have the same length k. Each word is used at most once.
    """
    if not words:
        return 0
    k = len(words[0])
    counts = Counter(words)
    pairs = 0
    has_center = False
    for w, c in counts.items():
        r = w[::-1]
        if w == r:
            pairs += c // 2
            if c % 2 == 1:
                has_center = True
        elif w < r:  # visit each {w, reverse(w)} group once
            pairs += min(c, counts.get(r, 0))
    return 2 * pairs * k + (k if has_center else 0)


def build_longest_palindrome(words: list[str]) -> str:
    """Return one longest palindrome, or "" if none exists.

    The left half is sorted and the smallest leftover palindrome is the
    center, so the output is deterministic."""
    counts = Counter(words)
    left: list[str] = []
    center = ""
    for w in sorted(counts):
        r = w[::-1]
        c = counts[w]
        if w == r:
            left.extend([w] * (c // 2))
            if c % 2 == 1 and (center == "" or w < center):
                center = w
        elif w < r:  # the group {w, r} is handled once, at its smaller word
            left.extend([w] * min(c, counts.get(r, 0)))
    left.sort()
    right = [w[::-1] for w in reversed(left)]
    return "".join(left) + center + "".join(right)


if __name__ == "__main__":
    assert longest_palindrome_length(["ab", "ty", "yt", "lc", "cl", "ab"]) == 8
    assert longest_palindrome_length(["ab", "ba", "cc", "cc", "cc"]) == 10
    assert longest_palindrome_length(["xy", "zw"]) == 0
    assert longest_palindrome_length(["aa"]) == 2
    assert longest_palindrome_length([]) == 0
    assert longest_palindrome_length(["abc", "cba", "bab", "xyx"]) == 9
    assert longest_palindrome_length(["ab", "ba", "ba", "ba"]) == 4

    for ws in (
        ["ab", "ty", "yt", "lc", "cl", "ab"],
        ["ab", "ba", "cc", "cc", "cc"],
        ["abc", "cba", "bab", "xyx"],
        ["dd", "aa", "bb", "dd", "aa"],
        ["xy", "zw"],
    ):
        s = build_longest_palindrome(ws)
        assert s == s[::-1], s
        assert len(s) == longest_palindrome_length(ws), (ws, s)
        assert not (Counter(s[i:i + len(ws[0])] for i in range(0, len(s), len(ws[0])))
                    - Counter(ws)), (ws, s)
    assert build_longest_palindrome(["ab", "ba", "cc", "cc", "cc"]) == "abccccccba"
    assert build_longest_palindrome(["dd", "aa", "bb", "dd", "aa"]) == "aaddbbddaa"
    print("all tests pass")

Complexity

Let n be the number of words and k their length.

• longest_palindrome_length: O(n * k) time to count and reverse words; O(n * k) space for the counter.
• build_longest_palindrome: O(n * k log n) time for sorting (string compares cost up to k), plus O(n * k) to build the output; O(n * k) space.
• If k is a small constant (the common two-letter version), both are O(n) / O(n log n).

Test cases

• ["ab", "ty", "yt", "lc", "cl", "ab"] -> 8 (for example "tylcclyt"; the two "ab" have no "ba").
• ["ab", "ba", "cc", "cc", "cc"] -> 10, string "abccccccba" (one cc pair plus a cc center).
• ["dd", "aa", "bb", "dd", "aa"] -> 10, string "aaddbbddaa" (bb is the smallest leftover palindrome, so it is the center).
• ["abc", "cba", "bab", "xyx"] -> 9 ("abc" + "bab" + "cba"; only one center is allowed).
• ["ab", "ba", "ba", "ba"] -> 4 (extra copies of "ba" have no partner).
• ["xy", "zw"] -> 0, string "".
• ["aa"] -> 2 (a single palindromic word is a valid answer).
• [] -> 0.

Follow-ups

1. Return the palindrome, not just its length. Collect the left half while counting, then mirror it as in build_longest_palindrome. For a deterministic answer, sort the left half and pick the smallest leftover palindrome as the center. For the true lexicographically smallest answer, also note that each left word may be placed as w or reverse(w), so choose the smaller of the two before sorting.
2. Words of different lengths. Boundaries no longer line up, so simple pairing fails ("ab" + "a" is "aba"). Treat it as a search over an "unmatched overhang" string: put words on the left or right side, cancel the matching characters, and keep the leftover suffix or prefix as the state. States are suffixes/prefixes of words, so a trie of words and reversed words plus memoized DFS over (state, multiset used) works for small n. In general it is exponential; say so, and bound n. This is the "Palindrome Pairs" trie idea, extended to many words.
3. Streaming words. Keep the counter and a running pairs and odd_palindromes count. On each insert, check whether the new word completes a pair with its reverse or flips a palindrome's parity. Each update is O(k) and the length is available in O(1).
4. Weighted words (maximize total score instead of length). Groups stay independent. For each {w, reverse(w)} group, take pairs while both weights are positive; for the center, pick the best leftover palindrome, and also consider breaking one palindromic pair if a single high-value copy beats it.
5. Very large input (does not fit in memory). Normalize each word to min(w, reverse(w)) and count with an external sort or a sharded map-reduce by that key. Each shard computes its pairs and whether it has an odd palindrome; combine with a sum and an OR.

Interviewer expectations

Mid-level (L4)

• Sees that word i must mirror word m - 1 - i because all words have the same length.
• Writes the counter solution with correct handling of palindromic words and a single center.
• Avoids double counting {w, reverse(w)} and tests the empty and no-answer cases.

Senior (L5)

• Explains why greedy pairing is optimal (independent groups, one center slot).
• Builds the actual string and proves it is a palindrome; handles determinism or lexicographic order.
• Gives exact complexity in terms of n and k and handles the streaming follow-up cleanly.

Staff (L6+)

• States clearly why the mixed-length version breaks the pairing argument and frames the state-space search with tries, including its exponential worst case.
• Discusses the weighted and distributed variants and when to change the data model.
• Drives the conversation: clarifies constraints early (equal lengths, duplicates, return type) before coding.