We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Largest Palindromic Number

Difficulty: Medium

Problem Description

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.

Key Insights

  • A palindromic number reads the same forwards and backwards.
  • To construct the largest palindromic number, we can use a frequency count of the digits.
  • The digits used in the first half of the palindrome can mirror in the second half.
  • If an odd frequency digit exists, it can be placed in the middle of the palindrome.
  • Leading zeros need to be avoided unless the only digit is zero.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the input string. Space Complexity: O(1), since we only need a fixed-size array for digit counts.

Solution

To solve the problem, we will:

  1. Count the frequency of each digit from 0 to 9 using an array.
  2. Construct the first half of the palindrome using the available digits, starting from the largest digit to ensure the largest number.
  3. If there exists any digit with an odd count, we will select the largest one to place in the middle of the palindrome.
  4. Mirror the first half to form the second half of the palindrome.
  5. Handle leading zeros by ensuring the result does not start with '0', unless it is the only digit.

Code Solutions

def largest_palindromic(num: str) -> str:
    count = [0] * 10
    for digit in num:
        count[int(digit)] += 1
    
    first_half = []
    middle_digit = ''
    
    for digit in range(9, -1, -1):
        if count[digit] > 0:
            # If count is odd, we can place this digit in the middle if it's larger than current middle
            if count[digit] % 2 == 1 and middle_digit == '':
                middle_digit = str(digit)
            # Add the half count (floor of count / 2) to the first half
            first_half.append(str(digit) * (count[digit] // 2))
    
    # Join first half
    first_half_str = ''.join(first_half)
    # Create the palindrome
    if first_half_str == '' and middle_digit == '':
        return '0'  # Edge case for all zeros
    result = first_half_str + middle_digit + first_half_str[::-1]
    
    # Check for leading zeros
    if result[0] == '0':
        return '0'
    
    return result
← Back to All Questions