Solution: Largest Palindromic Number

Grokking the Coding Interview: Patterns for Coding Questions

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Largest Palindromic Number

Table of Contents

Contents are not accessible

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<sup>5</sup>
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:

Python3

. . . .

Complexity Analysis

Time Complexity: $O(n)$ , 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: $O(n)$ , where (n) is the length of the input string.
- Frequency Array: $O(10) \approx O(1)$ space.
- First Half StringBuilder: Up to $O(n)$ space in the worst case.
- Middle String: $O(1)$ space.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible