#2384

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Largest Palindromic Number

Form the largest palindromic number from a string of digits while maintaining a valid palindrome structure.

Problem Statement

You are given a string num consisting of digits only. Your task is to return the largest palindromic integer that can be formed using the digits of num, in string form. The palindrome must not contain leading zeroes unless the result is zero itself.

In order to form a valid palindrome, for each digit, it must appear in pairs (except for possibly one digit that can be placed in the middle for odd-length palindromes). The goal is to find the largest palindrome possible, which may involve discarding unused digits.

Examples

Example 1

Input: num = "444947137"

Output: "7449447"

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"

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 Approach

Greedy Approach with Counting

Count the frequency of each digit, ensuring each one can form pairs. Greedily choose the largest possible digits to form the outer parts of the palindrome while leaving one central digit if necessary.

Palindrome Validation

To ensure the number is palindromic, digits must appear in pairs except for a single middle digit in odd-length cases. Validate the structure after constructing the palindrome.

Efficient Digit Management

Manage the digits efficiently using a hash table (or frequency array). This allows for quick access and adjustment as we form the palindrome and ensures that no leading zeroes appear unless the palindrome is zero.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the approach used for digit counting and palindrome construction. In the worst case, it involves iterating through the string and processing digits, resulting in O(n) time complexity, where n is the length of the string. Space complexity is O(1) if using a fixed-size array for digit counts, or O(k) where k is the number of unique digits, typically 10.

What Interviewers Usually Probe

Can the candidate efficiently count the digits and form the largest possible palindrome?
Is the candidate aware of edge cases like leading zeroes or the structure of palindromes?
Does the candidate demonstrate an understanding of how to optimize the palindrome construction process?

Common Pitfalls or Variants

Common pitfalls

Not handling the case where digits are not paired properly, leading to an invalid palindrome.
Overlooking the possibility of leading zeroes in the final result.
Failing to maximize the palindrome size by not greedily selecting the largest available digits.

Follow-up variants

Form a palindrome from a string of digits with constraints on the number of allowed digits.
Allow the use of a subset of digits for palindrome formation.
Form a palindrome where the middle digit must be the smallest possible digit.

FAQ

How do I approach solving the Largest Palindromic Number problem?

Use a greedy approach combined with digit counting. Ensure digits form pairs, and leave one possible middle digit for odd-length palindromes.

What is the time complexity of solving this problem?

The time complexity is O(n), where n is the length of the string, due to the need to count and process each digit.

Can leading zeroes appear in the final palindrome?

No, leading zeroes should not appear in the result unless the palindrome is exactly zero.

What is the greedy choice strategy in this problem?

The greedy strategy involves selecting the largest available digits for the palindrome, ensuring that digits are paired and the result is the largest possible palindrome.

How does GhostInterview assist with this problem?

GhostInterview guides you through the digit counting process and ensures that the final palindrome is correctly formed while avoiding common pitfalls like leading zeroes.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def largestPalindromic(self, num: str) -> str:
        cnt = Counter(num)
        ans = ''
        for i in range(9, -1, -1):
            v = str(i)
            if cnt[v] % 2:
                ans = v
                cnt[v] -= 1
                break
        for i in range(10):
            v = str(i)
            if cnt[v]:
                cnt[v] //= 2
                s = cnt[v] * v
                ans = s + ans + s
        return ans.strip('0') or '0'

Continue Practicing

#2182 construct string with repeat limit #2131 longest palindrome by concatenating two letter words #3016 minimum number of pushes to type word ii