2384. Largest Palindromic Number - Detailed Explanation

Problem Statement

Description:
Given a string num consisting of digits, rearrange and choose some of the digits (if necessary) to form the largest palindromic number. The resulting number should not have extra leading zeros unless the number is exactly "0".

Examples:

Example 1:

• Input: "444947137"
• Output: "7449447"
• Explanation:
  Count the occurrences of each digit. The best palindrome is formed by pairing digits (from highest to lowest) and possibly using one digit in the center. Here, by choosing two 7's, two 4's, two 9's, and one 1 or 3 for the center, the optimal arrangement results in "7449447".

Example 2:

• Input: "00009"
• Output: "9"
• Explanation:
  Although there are several zeros, using them would create leading zeros. The largest valid palindrome is simply "9".

Example 3:

• Input: "12321"
• Output: "32123"
• Explanation:
  The available digits can be rearranged. However, note that the answer must be a palindrome. One optimal solution is "32123", where the left half is "32", the middle digit is "1", and the right half is the reverse "23". (Depending on the digits available, multiple palindromic arrangements might exist, but the goal is to form the numerically largest one.)

Constraints:

• 1 ≤ num.length ≤ 10⁵
• num consists only of digits from '0' to '9'.

Hints

1. Digit Frequency:
   Start by counting how many times each digit appears. This will help you decide which digits can form pairs for the left and right halves of the palindrome.

2. Choosing the Center:
   A palindrome can have a center digit (if the total number of occurrences of that digit is odd). For the largest palindrome, consider using the highest digit available that has an odd frequency as the center.

3. Pairing Digits:
   To maximize the numeric value, try to use as many of the higher digits as possible in the outer pairs. Remember, when forming the left half, arrange the digits in descending order.

Approach Overview

Brute Force Approach

• Idea:
  Generate all possible rearrangements of the digits, check which rearrangements form a palindrome, and then select the largest one.
• Drawbacks:
  This method quickly becomes infeasible as the length of the input increases due to the factorial growth of permutations.
• Conclusion:
  Not practical for inputs with even moderate length.

Optimal Approach Using Frequency Count

• Idea:

  • Step 1: Count the frequency of each digit (0 through 9).

  • Step 2: Form pairs from the available digits. For each digit from 9 down to 0, use as many pairs as possible (i.e., frequency // 2).

  • Step 3: Check for any leftover digit (with an odd frequency) that can be used as the center. Always choose the highest available digit for the center.

  • Step 4: Build the left half of the palindrome by appending each digit (the number of times equal to the pair count) in descending order. The right half is simply the reverse of the left half.

  • Step 5: Combine the left half, center (if any), and right half to form the final palindromic number.

• Example Walkthrough:
  Consider "444947137". Count the digits and see that:

  • Digit 9 appears once (cannot form a pair, but might be used as a center if no higher digit qualifies).

  • Digit 7 appears twice.

  • Digit 4 appears four times.

  • Digits 1 and 3 appear once each.

  Use the pairs for 7 and 4, and then choose the best candidate for the center (here, choosing 9 or 7 could be possible, but the algorithm will ensure the final number is maximized by taking the highest odd available). Arrange the left half in descending order (e.g., "7449" might be a part) and mirror it.

• Time Complexity: O(n + k) where n is the length of the input and k is the number of digits (constant 10)

• Space Complexity: O(1) for the digit frequency array and additional strings.

Code Implementation

Python Code