medium Largest Palindromic Number

Problem Statement

Given a string s containing 0 to 9 digits, create the largest possible palindromic number using the string characters. It should not contain leading zeroes.

A palindromic number reads the same backward as forward.

If it's not possible to form such a number using all digits of the given string, you can skip some of them.

Examples

Example 1

Input: s = "323211444"
Expected Output: "432141234"
Justification: This is the largest palindromic number that can be formed from the given digits.

Example 2

Input: s = "998877"
Expected Output: "987789"
Justification: "987789" is the largest palindrome that can be formed.

Example 3

Input: s = "54321"
Expected Output: "5"
Justification: Only "5" can form a valid palindromic number as other digits cannot be paired.

Constraints:

1 <= num.length <= 10⁵
num consists of digits.

Try it yourself

Try solving this question here:

🎯 STRICT STANDOUT — Largest Palindromic Number — problem

0. Pattern family

Family: Greedy digit frequency palindrome build

1. Why / judgment (K3)

Count digits 0-9; put largest available pairs on outside; optional single middle from largest leftover odd; strip leading zeros carefully ("0" edge).

1a. Reference solution — frequency-greedy build

A palindrome is a left half + optional middle + the mirrored left half. To make it as large as possible: build the left half from the biggest digits first using each digit's pairs (count[d]/2 copies), scanning 9→0; then set the middle to the largest digit that still has an odd leftover; then mirror.

public String largestPalindromic(String num) {
    int[] count = new int[10];
    for (char c : num.toCharArray()) count[c - '0']++;

    // 1. Left half: largest digits first, count[d]/2 pairs each.
    StringBuilder half = new StringBuilder();
    for (int d = 9; d >= 0; d--)
        for (int i = 0; i < count[d] / 2; i++)
            half.append((char) ('0' + d));

    // 2. Leading-zero rule (b): if the half starts with '0' then NO non-zero
    //    pair exists (we scanned 9..0), so the whole half is zeros that could
    //    only lead -> discard them. (Interior zeros, e.g. "10001", survive
    //    because a larger digit sits in front of them.)
    int start = 0;
    while (start < half.length() && half.charAt(start) == '0') start++;
    String left = half.substring(start);

    // 3. Middle = largest digit with an odd leftover count.
    String mid = "";
    for (int d = 9; d >= 0; d--)
        if (count[d] % 2 == 1) { mid = String.valueOf((char) ('0' + d)); break; }

    // 4. Assemble. Leading-zero rule (a): empty result means only zeros (or
    //    nothing usable) were available -> the answer is "0".
    String right = new StringBuilder(left).reverse().toString();
    String ans = left + mid + right;
    return ans.isEmpty() ? "0" : ans;
}

Build trace of Example 1, s = "323211444":

counts: count[1]=2, count[2]=2, count[3]=2, count[4]=3  (rest 0)
half (scan 9→0, count[d]/2 copies):
   d=4: 3/2 = 1 copy → "4"
   d=3: 2/2 = 1 copy → "43"
   d=2: 2/2 = 1 copy → "432"
   d=1: 2/2 = 1 copy → "4321"        left = "4321" (no leading zero to strip)
middle (largest odd leftover): count[4]=3 is odd → mid = "4"
mirror: right = reverse("4321") = "1234"
answer = "4321" + "4" + "1234" = "432141234"  ✓

Leading-zero rules (the tricky part):

Rule (a) — all-zero / nothing usable → "0". If there is no non-zero pair and no non-zero single, the assembled string is empty; return the single digit "0". Example: s="00" → half is "0", stripped to empty, no odd digit → "0" (not "00").
Rule (b) — never let 0 lead the outer half. Because the half is built scanning 9→0, a leading '0' can only appear when no larger pair exists, so those zeros are stripped. A 0 may still sit in the interior or as the middle: s="10001" → half "10" (the leading '1' protects the interior 0), mid "0" → "10001".

2. Worked complexity / derivation (K11)

O(n + |Σ|) with Σ=10. Sort not needed if scan 9→0.

3. Pattern + recognition + when-NOT (K12)

Name: FREQUENCY PALINDROME GREEDY

Recognition: largest numeric palindrome from digit multiset; no leading zero.

When-NOT: Longest palindromic subsequence length. Next palindrome number different.

4. Edge hand-run (K13)

444947137 -> 7449447. All zeros -> 0. Single non-zero.

5. Interviewer follow-ups & drills

Q1. Leading zeros?
Model answer: If first half empty after pairs of 0 only → answer "0" or middle.

Q2. Middle choice?
Model answer: Largest digit with odd remaining count.

Q3. Why not sort string reverse?
Model answer: Must respect palindrome structure + multiset limits.

✅ Solution Largest Palindromic Number

Problem Statement

Given a string s containing 0 to 9 digits, create the largest possible palindromic number using the string characters. It should not contain leading zeroes.

A palindromic number reads the same backward as forward.

If it's not possible to form such a number using all digits of the given string, you can skip some of them.

Examples

Example 1

Input: s = "323211444"
Expected Output: "432141234"
Justification: This is the largest palindromic number that can be formed from the given digits.

Example 2

Input: s = "998877"
Expected Output: "987789"
Justification: "987789" is the largest palindrome that can be formed.

Example 3

Input: s = "54321"
Expected Output: "5"
Justification: Only "5" can form a valid palindromic number as other digits cannot be paired.

Constraints:

1 <= num.length <= 10⁵
num consists of digits.

Solution

To solve this problem, the goal is to create the largest palindromic number possible using the digits from the given input number. A palindrome reads the same backward as forward, so our approach is to build the number symmetrically.

First, we count the frequency of each digit in the input number using an array of size 10 (for digits 0-9). Then, we construct the first half of the palindrome by appending each digit as many times as half of its frequency, starting from the highest digit (9) down to the lowest (0). If there is a digit with an odd frequency, we select the largest such digit to be the center of the palindrome. Finally, we append the reversed first half to the original first half (with the center digit, if any) to complete the palindrome. This ensures that the number is the largest possible palindrome.

Step-by-Step Algorithm

Initialize Data Structures:
- Create a StringBuilder named firstHalf to store the first half of the palindrome.
- Create an integer array frequency of size 10 to count the frequency of each digit (0-9).
- Initialize a variable middle to -1 to store the center digit if needed.
Count Frequencies:
- Iterate through each character in the input string num.
- For each character, convert it to an integer and increment its corresponding frequency in the frequency array.
Build the First Half of the Palindrome:
- Iterate from the highest digit (9) to the lowest digit (0).
- For each digit, if its frequency is greater than 1:
  - Use while loop to add pairs of the digit to firstHalf until less than 2 of that digit remains.
  - If there is one of the digit left and middle is still -1, set middle to this digit (largest odd-count digit).
Build the Full Palindrome:
- Create secondHalf as a reversed copy of firstHalf.
- If middle is not -1, append middle to firstHalf.
- Append the reversed secondHalf to firstHalf.
Return the Result:
- If firstHalf has any digits, return firstHalf as the final palindrome.
- Otherwise, return "0".

Algorithm Walkthrough

Initialize Data Structures:
- firstHalf = ""
- frequency = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
- center = -1
Count Frequencies:
- Process each digit in num:
  - 3: frequency[3] becomes 1.
  - 2: frequency[2] becomes 1.
  - 3: frequency[3] becomes 2.
  - 2: frequency[2] becomes 2.
  - 1: frequency[1] becomes 1.
  - 1: frequency[1] becomes 2.
  - 4: frequency[4] becomes 1.
  - 4: frequency[4] becomes 2.
  - 4: frequency[4] becomes 3.
- Final frequency = [0, 2, 2, 2, 3, 0, 0, 0, 0, 0]
Build the First Half of the Palindrome:
- Iterate from digit 9 to 0:
  - 9: frequency[9] is 0, skip.
  - 8: frequency[8] is 0, skip.
  - 7: frequency[7] is 0, skip.
  - 6: frequency[6] is 0, skip.
  - 5: frequency[5] is 0, skip.
  - 4: frequency[4] is 3:
    - Append "4" to firstHalf, firstHalf = "4", count becomes 1.
    - center is set to 4 since it's the largest digit with an odd frequency.
  - 3: frequency[3] is 2:
    - Append "3" to firstHalf, firstHalf = "43", count becomes 0.
  - 2: frequency[2] is 2:
    - Append "2" to firstHalf, firstHalf = "432", count becomes 0.
  - 1: frequency[1] is 2:
    - Append "1" to firstHalf, firstHalf = "4321", count becomes 0.
  - 0: frequency[0] is 0, skip.
- Final firstHalf = "4321"
Build the Full Palindrome:
- Create secondHalf as a reversed copy of firstHalf, secondHalf = "1234".
- center is 4, so add 4 to firstHalf, making it 43214.
- Append secondHalf to firstHalf, firstHalf = "432144321".
Return the Result:
- firstHalf has digits, so return firstHalf.toString(), which is "432144321".

So, the largest palindromic number that can be formed from "323211444" is "432144321".

Code

Here is the code for this algorithm:

java

import java.util.Arrays; // Import Arrays class

public class Solution {

  public String largestPalindromic(String s) {
    StringBuilder firstHalf = new StringBuilder(); // StringBuilder to store first half of the palindrome
    int[] frequency = new int[10]; // Frequency array for digits 0-9

    // Count the frequency of each digit in the input number
    for (int i = 0; i < s.length(); i++) {
      int val = (s.charAt(i) - '0');
      frequency[val] += 1;
    }

    int middle = -1; // Variable to store the middle digit if needed

    // Iterate from the highest digit (9) to the lowest (0)
    for (int i = 9; i >= 0; i--) {
      if (frequency[i] != 0 && (i != 0 || firstHalf.length() > 0)) {
        int count = frequency[i];
        while (count > 1) {
          firstHalf.append(i); // Append the digit to firstHalf
          count -= 2; // Use two of the digit for the first half
        }
        if (count == 1 && middle == -1) {
          middle = i; // Assign the middle digit if it's the largest odd-count digit
        }
      }
    }

    StringBuilder secondHalf = new StringBuilder(firstHalf); // Create secondHalf as a reversed copy of firstHalf
    if (middle != -1) firstHalf.append(middle); // Append the middle digit if it exists
    firstHalf.append(secondHalf.reverse()); // Append the reversed first half to firstHalf

    return firstHalf.length() > 0 ? firstHalf.toString() : "0"; // Return the final palindrome or "0"
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    System.out.println(solution.largestPalindromic("323211444")); // 432141234
    System.out.println(solution.largestPalindromic("998877")); // 987789
    System.out.println(solution.largestPalindromic("54321")); // 5
  }
}

Complexity Analysis

Time Complexity: , where n is the length of the input string. The algorithm involves iterating over the input string once for frequency counting and then iterating over the frequency array (constant size of 10).
Space Complexity: Space Complexity: , where (n) is the length of the input string.
- Frequency Array: space.
- First Half StringBuilder: Up to space in the worst case.
- Middle String: space.

🎯 STRICT STANDOUT — Solution Largest Palindromic Number

0. Pattern family

Family: Digit freq palindrome construction

1. Why / judgment (K3)

freq[10]; build left half 9→0 taking count//2; pick mid; mirror left. Handle all-zero and leading zero.

2. Worked complexity / derivation (K11)

O(n) count + O(1) build (half length ≤ n/2).

3. Pattern + recognition + when-NOT (K12)

Name: GREEDY MULTISET PALINDROME

Recognition: largest palindrome number string from digits.

When-NOT: Any palindrome existence only → different. Lexicographic string palindrome without numeric rules.

4. Edge hand-run (K13)

0000 -> 0. 0001 -> 1001 (pairs of 0 with mid 1). 10 -> 1.

5. Interviewer follow-ups & drills

Q1. Why 9→0?
Model answer: Largest digits outer.

Q2. Odd counts?
Model answer: At most one mid digit from leftover.

Q3. Empty left half?
Model answer: Return mid or "0".

🧩 Pattern · Arrays

Recognize it: Scan once tracking what you need (running max/sum), or precompute a prefix-sum / hash → turn O(n²) into O(n).

▶ Visualize this problem (step it, predict each fork)

⛶ Open this problem debugger in explore mode

🤖 Don't fully get this? Learn it with Claude

Stuck on Largest Palindromic Number? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Largest Palindromic Number** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Largest Palindromic Number** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Largest Palindromic Number**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Largest Palindromic Number**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Count and Say Longest Increasing Subsequence →