Largest Palindrome by Permuting Digits

Largest Palindrome by Permuting Digits asks you to rearrange a bag of digits into the biggest number that reads the same forwards and backwards. The trick is pure greedy: place the largest digits where they matter most.

The slow way first

The brute force is to generate every permutation of the digits, keep only the ones that are palindromes, and take the maximum. With n digits that is up to n! arrangements — hopelessly slow even for a dozen digits.

The question to ask: what does a palindrome actually require? Every digit except possibly one in the dead center must appear an even number of times — it shows up mirrored on both halves. So the problem is really about pairs, not permutations.

The idea: pair up, mirror, center the biggest

Count how many times each digit appears. Then walk the digits from 9 down to 0. Each digit contributes count // 2 copies to the left half (those will be mirrored on the right). If a digit has an odd count, one copy is left over — the largest such leftover becomes the single center digit.

Building the half from the highest digit down guarantees the most significant positions hold the biggest digits — which is exactly what makes the final number as large as possible.

Walk through it

Step through the animation. The pointer scans digits from high to low. 9×2 gives one pair → half is "9". 8×3 gives one pair → half is "98", with one 8 left over, which we remember as the center. 5×1 has no pair and is smaller than 8, so it is dropped. Finally we mirror: "98" + "8" + "89" = 98889.

Pseudocode

count[d] = how many times digit d appears
half = ""
middle = ""
for d from 9 down to 0:
    half += str(d) repeated (count[d] // 2) times
    if count[d] is odd and middle is still empty:
        middle = str(d)            # largest odd-count digit
return half + middle + reverse(half)

The Python solution

def largest_palindrome(digits):
    count = [0] * 10
    for d in digits: count[d] += 1
    half, middle = "", ""
    for d in range(9, -1, -1):
        pair = count[d] // 2
        half += str(d) * pair
        if count[d] % 2 and middle == "":
            if d > 0 or half:
                middle = str(d)
    return half + middle + half[::-1]

• count tallies each digit 0..9 in a single pass.
• We loop d from 9 down to 0 so the biggest digits land in the most significant places.
• pair = count[d] // 2 is how many mirrored copies this digit supplies; we append them to half.
• The if count[d] % 2 and middle == "" check captures the first odd-count digit we meet going high-to-low — that is the largest, and it owns the center.
• d > 0 or half avoids a leading-zero center on an all-zero input.
• half + middle + half[::-1] glues the left half, the optional center, and the reversed half together.

Complexity

Counting is O(n) and the digit loop is a fixed 10 iterations, so the whole thing is linear in the number of digits with constant extra space (a size-10 count array).

When this pattern shows up

Practice