LeetCode 2384 - Largest Palindromic Number

The problem asks us to form the largest palindromic integer using the digits from a given string num. A palindrome is a number that reads the same forwards and backwards, like 121 or 7449447. The input string num consists only of digits (0 to 9) and may include repeated digits.

leetcodemediumhash-tablestringgreedycounting

LeetCode Problem 2384

Difficulty: 🟡 Medium
Topics: Hash Table, String, Greedy, Counting

Solution

Problem Understanding

The problem asks us to form the largest palindromic integer using the digits from a given string num. A palindrome is a number that reads the same forwards and backwards, like 121 or 7449447. The input string num consists only of digits (0 to 9) and may include repeated digits. We can reorder the digits, and we are allowed to use some or all of them, but at least one digit must be used. The result must not have leading zeros, except in the trivial case where the number is 0.

For example, if num is "444947137", the largest palindrome we can form is "7449447". The key here is that palindromes are symmetric, so we need to balance digits on both sides and optionally place a single digit in the center if needed.

The constraints indicate that num can be up to 100,000 characters long, so we need an algorithm that is linear or near-linear in time. Edge cases to consider include:

  • Strings with all zeros, e.g., "0000" (should return "0").
  • Strings with only one digit, e.g., "7" (should return "7").
  • Strings where the largest palindrome cannot use all digits due to symmetry.

Approaches

A brute-force approach would generate all permutations of the digits, check each for being a palindrome, and then pick the largest. This is correct but completely impractical for large input lengths due to factorial time complexity.

The key insight for an optimal solution is that a palindrome is defined by its left half and optionally a center digit. Therefore, we can:

  1. Count the occurrences of each digit.
  2. Use the highest digits first to build the left half of the palindrome.
  3. If any digit remains (occurs an odd number of times), we can place the largest remaining digit in the middle.
  4. Mirror the left half to form the right half.

This reduces the problem to counting and greedy selection, making it feasible for large inputs.

Approach Time Complexity Space Complexity Notes
Brute Force O(n!) O(n!) Generate all permutations and filter palindromes. Not feasible.
Optimal O(n) O(1) Count digits and build the palindrome greedily from highest to lowest. Digit counts are fixed at 10.

Algorithm Walkthrough

  1. Initialize a count array of size 10 to store occurrences of each digit from 0 to 9.
  2. Iterate through num and increment the count for each digit.
  3. Initialize an empty string left_half for the left side of the palindrome.
  4. For digits 9 down to 0, append count[digit] // 2 copies of the digit to left_half. Reduce count[digit] by 2 * (count[digit] // 2).
  5. Identify a middle digit: the largest digit d with count[d] > 0. This will be the center of the palindrome.
  6. Form the full palindrome as left_half + middle + reversed(left_half).
  7. Handle the edge case where the resulting palindrome starts with '0'. If so, the entire number must be "0" (all digits were zero).

Why it works: By using the largest digits first for both halves, we maximize the numeric value. The symmetry of the palindrome is guaranteed by mirroring left_half. Selecting the largest odd-count digit for the middle ensures the overall value is maximized.

Python Solution

class Solution:
    def largestPalindromic(self, num: str) -> str:
        count = [0] * 10
        for ch in num:
            count[int(ch)] += 1

        left_half = []
        for d in range(9, -1, -1):
            if count[d] >= 2:
                times = count[d] // 2
                left_half.append(str(d) * times)
                count[d] -= times * 2

        left_str = ''.join(left_half)
        middle = ''
        for d in range(9, -1, -1):
            if count[d] > 0:
                middle = str(d)
                break

        # Remove leading zeros if the left half is empty
        if left_str and left_str[0] == '0':
            left_str = ''
            middle = '0' if middle else '0'

        return left_str + middle + left_str[::-1]

Explanation: We count digits and greedily build the left half using as many pairs of digits as possible, starting from 9. The middle digit is the largest leftover digit. We handle the case where all digits are zero by checking the first character.

Go Solution

func largestPalindromic(num string) string {
    count := [10]int{}
    for _, ch := range num {
        count[ch-'0']++
    }

    leftHalf := ""
    for d := 9; d >= 0; d-- {
        if count[d] >= 2 {
            times := count[d] / 2
            for i := 0; i < times; i++ {
                leftHalf += string('0' + d)
            }
            count[d] -= times * 2
        }
    }

    middle := ""
    for d := 9; d >= 0; d-- {
        if count[d] > 0 {
            middle = string('0' + d)
            break
        }
    }

    if len(leftHalf) > 0 && leftHalf[0] == '0' {
        leftHalf = ""
        if middle == "" {
            middle = "0"
        }
    }

    rightHalf := ""
    for i := len(leftHalf) - 1; i >= 0; i-- {
        rightHalf += string(leftHalf[i])
    }

    return leftHalf + middle + rightHalf
}

Go-specific notes: We use a fixed array of size 10 for counting digits. String concatenation is used for simplicity. Handling leading zeros requires checking the first character of leftHalf.

Worked Examples

Example 1: num = "444947137"

Step Count Array Left Half Middle
Count digits [0,1,1,2,4,0,0,1,0,0] "" ""
Build left half append '7' (1 pair) "7" ""
append '4' (2 pairs) "744" ""
Determine middle largest remaining digit 4 "4" 4
Final palindrome "744" + "4" + "447" "7449447"

Example 2: num = "00009"

Step Count Array Left Half Middle
Count digits [4,0,0,0,0,0,0,0,0,1] "" ""
Build left half all counts < 2 "" ""
Determine middle largest digit with count>0 = 9 "" 9
Final palindrome "" + "9" + "" = "9"

Complexity Analysis

Measure Complexity Explanation
Time O(n) Counting digits is O(n), building the palindrome is O(1) since there are only 10 digits.
Space O(1) Fixed array of size 10 for digit counts; other strings use negligible space relative to input.

The algorithm is highly efficient because it does not depend on permutations or sorting the entire input. We leverage the limited digit range to achieve constant-time operations after counting.

Test Cases

# Provided examples
assert Solution().largestPalindromic("444947137") == "7449447"  # normal case
assert Solution().largestPalindromic("00009") == "9"            # leading zeros

# Edge cases
assert Solution().largestPalindromic("0") == "0"                 # single zero
assert Solution().largestPalindromic("0000") == "0"              # all zeros
assert Solution().largestPalindromic("123") == "3"               # no repeats, largest single
assert Solution().largestPalindromic("112233") == "321123"       # multiple pairs
assert Solution().largestPalindromic("9876543210") == "9"       # only single digits, largest is 9
Test Why
"444947137" Validates forming largest palindrome with repeated digits
"00009" Checks handling of leading zeros and selecting middle digit
"0" Minimal input
"0000" All zeros edge case
"123" No digit repetition, largest single digit becomes palindrome
"112233" Multiple digit pairs form a larger palindrome
"9876543210" Only single digits, must pick the largest

Edge Cases

All zeros: Input like "0000" can easily produce a palindrome with leading zeros. Our implementation detects this and returns "0".

Single-digit input: Input "7" should return "7". Since there is only one digit, it naturally