# Largest Palindromic Number
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/largest-palindromic-number)
Canonical: https://scaleengineer.com/dsa/problems/largest-palindromic-number
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Hash Table, String
**Companies:** [Geico](https://scaleengineer.com/companies/geico), [smartnews](https://scaleengineer.com/companies/smartnews), [Bentley Systems](https://scaleengineer.com/companies/bentley-systems)
---
## Problem
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 "**44494** **7**13**7**" 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.

# Approaches
## Brute-Force by Generating Subsequences and Permutations
This is a naive and highly impractical approach. The idea is to generate every possible number that can be formed using a subset of the given digits, check if it's a palindrome, and keep track of the largest one found.
**Time:** O(2^N * N!) · **Space:** O(2^N * N!)
**Pros:** Conceptually simple to understand the goal of checking every possibility.
**Cons:** Extremely inefficient and computationally infeasible for the given constraints.; The time and space complexity are exponential, making it impossible to run for `num.length` up to 10^5.; Complex to implement correctly due to the generation of subsequences and permutations.
### Explanation
The brute-force method explores every possibility. It involves three major steps: generating subsequences, generating permutations of those subsequences, and validating each result.

1.  **Generate Subsequences:** First, generate all possible subsequences of the input string `num`. A string of length `N` has `2^N - 1` non-empty subsequences.
2.  **Generate Permutations:** For each subsequence, generate all unique permutations of its digits.
3.  **Check for Palindrome and Validity:** For each permutation, check if it represents a valid number (no leading zeros, unless it's the number "0") and if it's a palindrome.
4.  **Track Maximum:** Keep a variable to store the largest valid palindromic number found so far. Compare each new valid palindrome with the current maximum and update if it's larger.

This approach is computationally explosive. For `N = 10^5`, `2^N` is an astronomical number, making this method impossible to execute in practice. It's only feasible for very small `N`.

```java
// This is a conceptual outline and not a practical implementation due to extreme complexity.
public String largestPalindromic_bruteForce(String num) {
    String maxPalindrome = "";
    // 1. Generate all subsequences of num's characters
    // For each subsequence:
        // 2. Generate all unique permutations of the subsequence
        // For each permutation:
            // 3. Check if it's a valid number (no leading zeros)
            // 4. Check if it's a palindrome
            // 5. If it is, compare with maxPalindrome and update if larger
            //    (comparison by length, then lexicographically)
    // The actual implementation would be very complex and slow.
    return maxPalindrome;
}
```
### Algorithm
- Generate all non-empty subsequences of the input string `num`.
- For each subsequence, generate all of its unique permutations.
- For each permutation, check if it forms a valid number (no leading zeros, unless it's the single digit "0").
- If it's a valid number, check if it's a palindrome.
- Keep track of the largest valid palindromic number found. Comparison should be based on length first, then lexicographically.

## Greedy Construction with Frequency Count
The core idea is to construct the largest palindrome by making locally optimal choices. A large number has more digits and larger digits in more significant positions. A palindrome is symmetric around a central point. We can use pairs of digits to build the symmetric parts and the largest remaining single digit for the center. By counting digit frequencies, we can greedily build the first half of the palindrome from the largest digits ('9' down to '0'), then find the largest middle digit, and finally construct the full palindrome.
**Time:** O(N), where N is the length of the input string `num`. The frequency counting takes O(N), and the subsequent loops for construction run in time proportional to N in total, as each character is processed a constant number of times. · **Space:** O(N), where N is the length of the input string. This space is used to store the resulting palindrome string, which can have a length up to N. The frequency map uses constant space O(1).
**Pros:** Highly efficient with linear time complexity, making it suitable for large inputs.; Simple and elegant logic based on a greedy strategy.; Correctly handles all specified edge cases like leading zeros and single-digit palindromes.
**Cons:** Requires careful handling of edge cases, particularly the leading zero for the first half and the case where the result is just "0".
### Explanation
This efficient approach leverages the properties of palindromes and the goal of finding the largest number. Instead of generating possibilities, we directly construct the optimal one.

1.  **Count Digit Frequencies:** We first iterate through the input string `num` and count the occurrences of each digit from '0' to '9'. An integer array of size 10 is perfect for this.
2.  **Construct the First Half:** To make the resulting number as large as possible, the first half of the palindrome should be the largest possible number. We build this `firstHalf` by iterating from digit '9' down to '0'. For each digit `d`, we append it `count[d] / 2` times. This ensures the `firstHalf` is in descending order (e.g., "99887..."). A special check is needed to prevent leading zeros: we only add pairs of '0's if the `firstHalf` is already non-empty.
3.  **Find the Middle Digit:** A palindrome can have one central digit. This digit corresponds to one that appears an odd number of times in the input. To maximize the palindrome, we should choose the largest such digit. We find this by iterating from '9' down to '0' and picking the first digit we find with an odd count.
4.  **Assemble the Palindrome:** The final palindrome is formed by concatenating the `firstHalf` string, the `middle` digit (if one exists), and the reverse of the `firstHalf` string.
5.  **Edge Cases:** If the resulting string is empty (which can happen if `num` only contains pairs of '0's, like "00"), the answer must be "0". Our logic handles this, as well as cases where the result is a single digit (e.g., from input "00009", the result is "9").

```java
class Solution {
    public String largestPalindromic(String num) {
        int[] counts = new int[10];
        for (char c : num.toCharArray()) {
            counts[c - '0']++;
        }

        StringBuilder firstHalf = new StringBuilder();
        for (int i = 9; i >= 0; i--) {
            // A non-zero number cannot start with '0'.
            if (firstHalf.length() == 0 && i == 0) {
                continue;
            }
            int numPairs = counts[i] / 2;
            for (int j = 0; j < numPairs; j++) {
                firstHalf.append(i);
            }
        }

        String middle = "";
        for (int i = 9; i >= 0; i--) {
            if (counts[i] % 2 == 1) {
                middle = Integer.toString(i);
                break;
            }
        }

        StringBuilder secondHalf = new StringBuilder(firstHalf).reverse();
        String result = firstHalf.toString() + middle + secondHalf.toString();

        if (result.isEmpty()) {
            return "0";
        }
        
        return result;
    }
}
```
### Algorithm
- **Count Frequencies:** Create an integer array of size 10 to store the frequency of each digit ('0' through '9') from the input `num`.
- **Construct First Half:** Initialize an empty `StringBuilder`. Iterate from digit `i = 9` down to `0`. For each digit, append it `count[i] / 2` times to the `StringBuilder`. This greedily builds the largest possible first half of the palindrome. To avoid leading zeros, skip adding '0' if the `StringBuilder` is currently empty.
- **Find Middle Digit:** Find the largest digit that has an odd count. Iterate from `i = 9` down to `0`, and the first `i` where `count[i]` is odd will be the middle digit. Store it as a string.
- **Assemble Palindrome:** Create the second half by reversing the first half. Concatenate `firstHalf + middle + secondHalf`.
- **Handle Edge Cases:** If the final assembled string is empty (which happens if the input only contains an even number of '0's, e.g., "00"), the answer should be "0". Otherwise, return the assembled string.

# Solutions
### Java

```java
class Solution {
public
  String largestPalindromic(String num) {
    int[] cnt = new int[10];
    for (char c : num.toCharArray()) {
      ++cnt[c - '0'];
    }
    String mid = "";
    for (int i = 9; i >= 0; --i) {
      if (cnt[i] % 2 == 1) {
        mid += i;
        --cnt[i];
        break;
      }
    }
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < 10; ++i) {
      if (cnt[i] > 0) {
        cnt[i] >>= 1;
        sb.append(("" + i).repeat(cnt[i]));
      }
    }
    while (sb.length() > 0 && sb.charAt(sb.length() - 1) == '0') {
      sb.deleteCharAt(sb.length() - 1);
    }
    String t = sb.toString();
    String ans = sb.reverse().toString() + mid + t;
    return "".equals(ans) ? "0" : ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  string largestPalindromic(string num) {
    vector<int> cnt(10);
    for (char c : num)
      ++cnt[c - '0'];
    string mid = "";
    for (int i = 9; ~i; --i) {
      if (cnt[i] % 2) {
        mid += (i + '0');
        --cnt[i];
        break;
      }
    }
    string t = "";
    for (int i = 0; i < 10; ++i) {
      if (cnt[i]) {
        cnt[i] >>= 1;
        while (cnt[i]--) {
          t += (i + '0');
        }
      }
    }
    while (t.size() && t.back() == '0') {
      t.pop_back();
    }
    string ans = t;
    reverse(ans.begin(), ans.end());
    ans += mid + t;
    return ans == "" ? "0" : ans;
  }
};

```

### Python

```python
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'

```