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.

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

1. 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.

2. 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.

3. 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).

4. 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.

5. Return the Result:

   • If firstHalf has any digits, return firstHalf as the final palindrome.
   • Otherwise, return "0".

Algorithm Walkthrough

1. Initialize Data Structures:

   • firstHalf = ""
   • frequency = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
   • center = -1

2. 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]

3. 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"

4. 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".

5. 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:

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.