{x}
blog image

Largest Palindromic Number

You are given a string num consisting of digits only.

Return the largest palindromic integer (in the form of a string) that can be formed using digits taken from num. It should not contain leading zeroes.

Notes:

  • You do not need to use all the digits of num, but you must use at least one digit.
  • The digits can be reordered.

 

Example 1:

Input: num = "444947137"
Output: "7449447"
Explanation: 
Use the digits "4449477" from "444947137" to form the palindromic integer "7449447".
It can be shown that "7449447" is the largest palindromic integer that can be formed.

Example 2:

Input: num = "00009"
Output: "9"
Explanation: 
It can be shown that "9" is the largest palindromic integer that can be formed.
Note that the integer returned should not contain leading zeroes.

 

Constraints:

  • 1 <= num.length <= 105
  • num consists of digits.

Solution Explanation for Largest Palindromic Number

The problem asks to find the largest palindromic number that can be formed using digits from a given string num. The solution involves a greedy approach combined with counting digit frequencies.

Approach:

  1. Count Digit Frequencies: We first count the occurrences of each digit (0-9) in the input string num using a hash map (or array in some implementations).

  2. Find the Middle Digit (Optional): We iterate through the digits from 9 to 0. If a digit has an odd count, we use it as the middle digit of the palindrome and decrement its count. A palindromic number can have at most one digit in the middle that is not paired.

  3. Construct the Palindromic Number: We iterate again through the digits from 0 to 9. For each digit with a count greater than 0, we divide its count by 2 (integer division). This represents the number of pairs of that digit we can use. We append these pairs to the beginning and end of the string to build the palindrome. The middle digit (if any) is placed in the center.

  4. Handle Leading Zeros: After constructing the palindrome, we remove any leading zeros. If the resulting string is empty, we return "0".

Time Complexity Analysis:

  • Counting digit frequencies takes O(n) time, where n is the length of the input string num.
  • Iterating through digits (twice) takes O(1) time as there are only 10 digits.
  • Constructing the palindrome string takes at most O(n) time in the worst case (when all digits are the same).
  • Removing leading zeros takes O(n) time in the worst case.

Therefore, the overall time complexity of the solution is O(n).

Space Complexity Analysis:

  • The space used for the digit frequency count is O(1) because there are a fixed number of digits (10).
  • The space used for building the palindrome string is at most O(n) in the worst case.

Therefore, the overall space complexity is O(n).

Code Explanation (Python):

from collections import Counter
 
class Solution:
    def largestPalindromic(self, num: str) -> str:
        cnt = Counter(num)
        ans = ''
        for i in range(9, -1, -1): # Find middle digit (odd count)
            v = str(i)
            if cnt[v] % 2:
                ans = v
                cnt[v] -= 1
                break
        for i in range(10): # Build palindrome from pairs
            v = str(i)
            if cnt[v]:
                cnt[v] //= 2
                s = cnt[v] * v
                ans = s + ans + s
        return ans.strip('0') or '0' #Remove leading zeros or return "0"

The other language implementations follow a similar logic, using their respective data structures (arrays, hash maps, string builders) to achieve the same result. The key is the greedy approach of prioritizing larger digits and efficiently constructing the palindrome from the digit frequencies.