LeetCode Solutions Blog

Largest Palindromic Number

Number: 2475

Difficulty: Medium

Paid? No

Problem Description

Given a string of digits, form the largest possible palindromic number by reordering and selecting some (or all) of the digits. The final palindrome should not contain leading zeroes and at least one digit must be used.

Key Insights

Use a frequency count for each digit to determine how many pairs can be formed.
Form the left half of the palindrome by taking the maximum number of pairs of each digit starting from 9 down to 0.
If there is an odd frequency, choose the highest digit available as the middle element for a potential center.
After forming the left half, the right half is simply its reverse.
Edge-case: if the left half is empty (only zeros) then return "0" to handle leading zeros correctly.

Space and Time Complexity

Time Complexity: O(n + 10) ≈ O(n) because we count digits and then iterate over a fixed range of digits. Space Complexity: O(n) for storing the output string (and O(1) additional space for counting fixed 10 digits).

Solution

The solution counts the frequency of each digit in the input string. Then, using a greedy approach, it forms the left half of the palindrome by taking as many pairs of each digit as possible, processing digits from 9 down to 0 so that the resulting number is maximal. Next, if a digit with an odd frequency remains, the algorithm selects the highest such digit as the middle element of the palindrome. Finally, it constructs the complete palindrome by concatenating the left half, the middle digit (if any), and the reverse of the left half. A final check ensures that if the constructed palindrome would start with a zero (i.e., all digits are zero), it outputs "0" instead.

Code Solutions

# Function to build largest palindromic number from digits in the input string.
def largest_palindromic(num: str) -> str:
    # Count occurrences of each digit
    digit_count = [0] * 10
    for ch in num:
        digit_count[int(ch)] += 1

    left_half = []  # Will store the left half of the palindrome
    middle_digit = ""

    # Process digits from 9 to 0 to form the largest number
    for digit in range(9, -1, -1):
        # If we have an odd count and no chosen middle digit yet, pick this digit as a candidate.
        if digit_count[digit] % 2 == 1 and middle_digit == "":
            middle_digit = str(digit)
        # For forming pairs, use as many digits as possible (count // 2 pairs)
        pair_count = digit_count[digit] // 2
        left_half.append(str(digit) * pair_count)

    # Join the parts for left half. It is built from highest to lowest digits.
    left_half_str = "".join(left_half)
    
    # Handle the edge case where left_half_str has leading zeros.
    # If left_half_str is empty, then no pair was formed.
    # However, if the only digits available are zeros, we should return "0".
    if left_half_str and left_half_str[0] == '0':
        return "0"
    # Also if nothing was added in left_half_str but a middle digit is chosen (non-zero) or
    # the chosen middle is "0", the result is simply the middle digit.
    if not left_half_str and middle_digit:
        return middle_digit

    # Right half is reverse of left_half_str.
    right_half_str = left_half_str[::-1]
    # Construct final palindrome
    palindrome = left_half_str + middle_digit + right_half_str
    # Final check - if palindrome starts with '0', then all digits are zeros.
    if palindrome[0] == '0':
        return "0"
    return palindrome

# Example Usage:
if __name__ == "__main__":
    print(largest_palindromic("444947137"))  # Expected output: "7449447"
    print(largest_palindromic("00009"))      # Expected output: "9"