Problem Description

Given a string num that contains only digits, you need to find the largest possible palindromic integer that can be formed by rearranging the digits from num. The result should be returned as a string and must not have leading zeros.

A palindrome reads the same forwards and backwards. For example, "12321" is a palindrome.

Key requirements:

• You can use any subset of the digits from num (but must use at least one digit)
• You can rearrange the digits in any order
• The result must be a valid palindrome
• The result should be the largest possible palindromic number
• No leading zeros are allowed (except for the special case of "0" itself)

For example:

• If num = "129321", you could form "9219" as a palindrome by using digits 9, 2, 1, 9
• If num = "444947137", you could form "7449447" by arranging the digits appropriately

The solution approach counts the frequency of each digit, then builds the palindrome by:

1. Finding the largest odd-frequency digit to potentially place in the middle
2. Using pairs of digits symmetrically on both sides, starting from the largest digits
3. Handling the special case of leading zeros by stripping them (returning "0" if all digits are zeros)

Intuition

To form the largest palindrome, we need to think about the structure of palindromes and how to maximize the numerical value.

A palindrome has a mirror structure - the left half mirrors the right half. For even-length palindromes like "1221", every digit appears an even number of times. For odd-length palindromes like "12321", one digit can appear an odd number of times (the middle digit), while all others must appear an even number of times.

To maximize the value, we want larger digits in the most significant positions. Since a palindrome mirrors itself, placing a digit on the left automatically determines its position on the right. For example, if we place '9' at the leftmost position, we must also place '9' at the rightmost position.

This leads us to a greedy strategy:

1. Count how many times each digit appears in the input
2. For the middle position (if the palindrome has odd length), we can use one digit that appears an odd number of times - we should choose the largest such digit
3. For the symmetric pairs on both sides, we can use half of each digit's count, placing larger digits towards the outside to maximize the value

The key insight is that we build the palindrome from inside out. First, we identify if there's a middle digit (any digit with odd frequency, preferably the largest). Then we add pairs of digits symmetrically, starting from the smallest digits (which go near the middle) to the largest digits (which go on the outside).

The special case of leading zeros needs attention - if our constructed palindrome is all zeros except possibly a middle digit, we need to return just "0" instead of "000...000".

Learn more about Greedy patterns.

Solution Approach

The implementation uses a frequency counter to track digit occurrences and builds the palindrome strategically:

1. Count digit frequencies: Use Counter(num) to count how many times each digit ('0' through '9') appears in the input string.

2. Find the middle digit: Iterate from the largest digit '9' down to '0' to find the largest digit with an odd frequency. This digit will be placed in the middle of our palindrome:

   for i in range(9, -1, -1):
       v = str(i)
       if cnt[v] % 2:
           ans = v
           cnt[v] -= 1
           break

   We decrement its count by 1 since we're using one instance for the middle position.

3. Build symmetric pairs: Iterate from the smallest digit '0' to the largest '9'. For each digit with remaining count:

   for i in range(10):
       v = str(i)
       if cnt[v]:
           cnt[v] //= 2
           s = cnt[v] * v
           ans = s + ans + s

   • Divide the count by 2 (using integer division) to get the number of pairs
   • Create a string s with that many instances of the digit
   • Add s to both sides of the current answer: s + ans + s

   This builds the palindrome from inside out - smaller digits are placed closer to the middle, larger digits on the outside.

4. Handle leading zeros: The final step ans.strip('0') or '0' removes leading zeros from both ends. If the result becomes empty (all digits were zeros), return '0'.

The algorithm runs in O(n) time where n is the length of the input string, with O(1) extra space since we only store counts for 10 possible digits.

Example Walkthrough

Let's trace through the solution with num = "129321":

Step 1: Count digit frequencies

• '1': 2 times
• '2': 2 times
• '3': 1 time
• '9': 1 time

Step 2: Find the middle digit (largest odd-frequency digit)

• Start from '9': frequency is 1 (odd) ✓
• Take one '9' for the middle: ans = "9"
• Update count: '9' now has 0 remaining

Step 3: Build symmetric pairs from inside out

• Check '0': count is 0, skip
• Check '1': count is 2
  • Pairs to use: 2 ÷ 2 = 1 pair
  • Create string: s = "1" (one '1')
  • Add symmetrically: ans = "1" + "9" + "1" = "191"
• Check '2': count is 2
  • Pairs to use: 2 ÷ 2 = 1 pair
  • Create string: s = "2" (one '2')
  • Add symmetrically: ans = "2" + "191" + "2" = "21912"
• Check '3': count is 1
  • Pairs to use: 1 ÷ 2 = 0 pairs (integer division)
  • Skip (no pairs to add)
• Check '4' through '8': count is 0, skip
• Check '9': count is 0 (already used for middle), skip

Step 4: Handle leading zeros

• "21912" has no leading zeros
• Final answer: "21912"

Note how the algorithm builds from inside out: the middle '9' was placed first, then pairs of '1' were added around it, and finally pairs of '2' were added on the outside. This ensures larger digits are in more significant positions, creating the largest possible palindrome.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm performs the following operations:

• Counter(num) takes O(n) time where n is the length of the input string, as it needs to count the frequency of each character
• The first loop iterates from 9 to 0 (10 iterations), which is O(1) constant time
• The second loop iterates from 0 to 9 (10 iterations), and for each iteration with count cnt[v], it creates a string of length cnt[v] and performs string concatenation. Since we're dealing with digits 0-9, the total number of characters processed across all iterations is still bounded by n, making this O(n)
• strip('0') operation takes O(n) time in the worst case

Overall time complexity: O(n) + O(1) + O(n) + O(n) = O(n)

Space Complexity: O(n)

The space usage includes:

• Counter object storing at most 10 key-value pairs: O(1)
• The ans string which can grow up to length n in the worst case: O(n)
• Temporary string s created during concatenation, which in total across all iterations uses space proportional to the input size: O(n)

Overall space complexity: O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Building Order Leading to Suboptimal Results

The most critical pitfall in this solution is building the palindrome from smallest to largest digits (0 to 9), which places larger digits closer to the middle and smaller digits on the outside. This produces a smaller palindrome instead of the largest possible one.

Example: For input "129321", the current approach would:

• Find middle digit: '1' (odd count)
• Build from 0 to 9: places '2' pairs around '1', then '9' pairs around that
• Result: "92129" instead of the optimal "99199"

Solution: Reverse the building order to iterate from 9 down to 0:

# Instead of:
for digit in range(10):
    # builds smaller palindrome

# Use:
for digit in range(9, -1, -1):
    digit_str = str(digit)
    if digit_count[digit_str] > 0:
        digit_count[digit_str] //= 2
        half_string = digit_str * digit_count[digit_str]
        middle_char = half_string + middle_char + half_string

2. Not Handling All-Zero Edge Case Properly

When the input consists entirely of zeros (e.g., "0000"), the algorithm might attempt to build a palindrome like "000" which, after stripping leading zeros, becomes an empty string. The or '0' handles this, but developers might forget this edge case.

Solution: Always ensure the final return statement includes proper handling:

return middle_char.strip('0') or '0'

3. Misunderstanding the Strip Operation

Using strip('0') removes zeros from both ends, which is correct for palindromes. However, developers might mistakenly use lstrip('0') thinking they only need to remove leading zeros, forgetting that in a palindrome, trailing zeros are also leading zeros when read backwards.

4. Not Considering Single Non-Zero Digit with Multiple Zeros

For input like "00001000", after building the palindrome, you might get "10001". The algorithm should recognize that using just "1" is actually the largest valid palindrome since "10001" has leading zeros when considered as a number.

Solution: After stripping zeros, verify the result is still a valid palindrome and hasn't broken the symmetry:

result = middle_char.strip('0') or '0'
# Ensure the result maintains palindrome property after stripping