2384. Largest Palindromic Number

MediumGreedyHash TableString
Leetcode Link

Problem Description

You are given a string num that consists only of digits. The task is to construct the largest palindromic integer (representing it as a string) by reordering digits taken from num. A palindrome is a sequence that reads the same backward as forward (like "121" or "1331"). The resulting palindrome should not have leading zeroes, meaning it should not start with the digit '0' unless the palindrome is simply "0". It is also important to note that you can choose to use some or all the digits from num, but you must use at least one digit to construct the palindrome.

Intuition

The intuition behind the solution is to strategically utilize the digits in num to create the largest possible palindrome. To achieve this, we consider several factors:

  1. The largest digit should be placed in the middle of the palindrome for odd-length palindromes.
  2. Even-length palindromes are formed by placing mirrored digits around the center.
  3. Leading zeroes can be avoided by ensuring that we don't start the construction of the palindrome with zeroes, except if the largest palindrome is "0" itself.

With this in mind, the following steps are taken in the solution:

  1. Count the frequency of each digit in the string.
  2. Starting from the largest digit (9) and moving to the smallest (0), look for a digit that has an odd count.
    • This digit, if any, can be used as the central character in an odd-length palindrome.
    • Decrease its count by one and store it.
  3. Then, for each digit from 0 to 9, append half of the remaining count of that digit to both sides of the palindrome.
    • This creates the mirrored effect around the center.
  4. Finally, remove any leading zeroes (if they are not the only character) from the resulting string to maintain the 'no leading zero' constraint.
  5. If the resulting string is empty (which can happen if we start with lots of zeroes), return "0".

By following these steps, we utilize the counts of digits in such a way to maximize the integer value of the resulting palindrome.

Learn more about Greedy patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Solution Approach

The solution implemented above uses a greedy approach and some basic understanding of how palindromes are structured. Here's the step-by-step explanation of the solution:

  1. Import the Counter class from Python's collections module to count the frequency of each digit in the input string num. Counter(num) provides a dictionary-like object where keys are unique digits from num, and the values are counts of those digits.

  2. Initialize an empty string ans to accumulate the palindrome constructed so far.

  3. Iterate through the digits in descending order, from '9' to '0', to find a digit that occurs an odd number of times.

    • When such a digit is found (cnt[v] % 2), use it as the central digit of the palindrome (ans = v) only if the palindrome is meant to be of odd length. This digit will not have a mirrored counterpart.
    • Decrease the count of that digit by 1 and break the loop as we are interested in only one such digit for the center of the palindrome.

  4. Iterate through the digits again, this time starting from '0'. For each digit v:

    • Check if the digit has a non-zero count in cnt.
    • Divide the count by 2 (cnt[v] //= 2) because we place half on each side of the palindrome.
    • Create a string s by repeating the digit v, cnt[v] times.
    • Update the palindrome string ans by placing string s before and after the current ans.

  5. Before returning the result, use ans.strip('0') to ensure that there are no leading zeroes, unless the palindrome is '0'. If ans is an empty string at this point (meaning it was made up of only zeroes), simply return '0'.

In summary, the algorithm employs a counter to keep track of frequency, a greedy approach for constructing the largest palindrome from the center outwards, and simple string manipulation to assemble the final palindromic string, making sure to adhere to the constraints laid out in the problem description.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Example Walkthrough

Let's illustrate the solution approach with a small example where the input string num is "310133".

Following the solution steps:

  1. We count the frequency of each digit:

    1'1': 1, '3': 2, '0': 1

  2. We find that digit '1' occurs an odd number of times. It can be the central digit of the palindrome.

    After this step, our palindrome under construction looks like this:

    1"_ _ 1 _ _"

  3. Next, we iterate from digit ‘9’ to ‘0’ and add the digits in pairs around the central digit:

    • We skip '9', '8', '7', '6', '5', '4', and '2' because their count in num is zero.
    • For digit '3' (which has a count of 2), we will take one to place on each side of '1'.

    After updating, the palindrome is:

    1"_ 3 1 3 _"

    • Since '1' is already used as the central digit, we move to '0'. There's one '0', so we cannot form a pair (it's left out).

      Our palindrome is currently:

    1"3 1 3"
    • We've added all digits where possible. No further digits can be placed.

  4. There’s no need to trim leading zeroes since the palindrome does not start or end with '0'.

  5. If our constructed palindrome were empty (e.g., if num was just "0"s), we would return "0".

As a result, for the given num "310133", the largest palindromic integer we can construct is "313".

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def largestPalindromic(self, num: str) -> str:
5        # Create a counter for the digits in the input string
6        digit_count = Counter(num)
7        # Initialize the middle character of the palindrome as empty
8        middle = ''
9        # Initialize the first half of the palindrome as empty
10        half_palindrome = ''
11
12        # Loop from the largest digit to the smallest to construct the first half of the palindrome
13        for digit in range(9, -1, -1):
14            char = str(digit)
15            if digit_count[char] > 1:
16                # Add half of the even occurrences of the digit to the first half of the palindrome
17                # Only add non-zero digits or zero digits if other digits are already in the half_palindrome
18                if char != '0' or (char == '0' and half_palindrome != ''):
19                    half_palindrome += char * (digit_count[char] // 2)
20                # Leave any odd occurrence for potential use in the middle
21                digit_count[char] %= 2
22            if digit_count[char] == 1 and middle == '':
23                # Use the first odd-occurring digit as the middle character
24                middle = char
25                digit_count[char] -= 1
26
27        # Reverse the first half and concatenate with the middle and first half to form the palindrome
28        palindrome = half_palindrome + middle + half_palindrome[::-1]
29
30        # If after forming the palindrome, it is empty or only zeros, return '0'
31        if not palindrome or palindrome.lstrip('0') == '':
32            return '0'
33        else:
34            return palindrome
35
1import java.util.HashMap;
2import java.util.Map;
3
4public class Solution {
5    public String largestPalindromic(String num) {
6        // Create a counter for the digits in the input string
7        Map<Character, Integer> digitCount = new HashMap<>();
8        for (char c : num.toCharArray()) {
9            digitCount.put(c, digitCount.getOrDefault(c, 0) + 1);
10        }
11
12        // Initialize the middle character of the palindrome as empty
13        String middle = "";
14        // Initialize the first half of the palindrome as empty
15        StringBuilder halfPalindrome = new StringBuilder();
16
17        // Loop from the largest digit to the smallest to construct the first half of the palindrome
18        for (char digit = '9'; digit >= '0'; digit--) {
19            if (digitCount.containsKey(digit) && digitCount.get(digit) > 1) {
20                // Add half of the even occurrences of the digit to the first half of the palindrome
21                // Only add non-zero digits or zero digits if other digits are already in the halfPalindrome
22                if (digit != '0' || (digit == '0' && halfPalindrome.length() > 0)) {
23                    char[] chars = new char[digitCount.get(digit) / 2];
24                    java.util.Arrays.fill(chars, digit);
25                    halfPalindrome.append(new String(chars));
26                }
27                // Leave any odd occurrence for potential use in the middle
28                digitCount.put(digit, digitCount.get(digit) % 2);
29            }
30            if (digitCount.containsKey(digit) && digitCount.get(digit) == 1 && middle.isEmpty()) {
31                // Use the first odd-occurring digit as the middle character
32                middle = Character.toString(digit);
33                digitCount.put(digit, digitCount.get(digit) - 1);
34            }
35        }
36
37        // Reverse the first half and concatenate with the middle and first half to form the palindrome
38        String palindrome = halfPalindrome.toString() + middle + halfPalindrome.reverse().toString();
39
40        // If after forming the palindrome, it is empty or only zeros, return '0'
41        if (palindrome.isEmpty() || palindrome.replace("0", "").isEmpty()) {
42            return "0";
43        } else {
44            return palindrome;
45        }
46    }
47}
48
1#include <string>
2#include <map>
3#include <algorithm>
4
5class Solution {
6public:
7    std::string largestPalindromic(std::string num) {
8        // Create a counter for the digits in the input string
9        std::map<char, int> digitCount;
10        for (char c : num) {
11            digitCount[c]++;
12        }
13
14        // Initialize the middle character of the palindrome as empty
15        std::string middle = "";
16        // Initialize the first half of the palindrome as empty
17        std::string halfPalindrome = "";
18
19        // Loop from the largest digit to the smallest to construct the first half of the palindrome
20        for (char digit = '9'; digit >= '0'; digit--) {
21            if (digitCount[digit] > 1) {
22                // Add half of the even occurrences of the digit to the first half of the palindrome
23                // Only add non-zero digits or zero digits if other digits are already in the halfPalindrome
24                if (digit != '0' || (digit == '0' && !halfPalindrome.empty())) {
25                    halfPalindrome += std::string(digitCount[digit] / 2, digit);
26                }
27                // Leave any odd occurrence for potential use in the middle
28                digitCount[digit] %= 2;
29            }
30            if (digitCount[digit] == 1 && middle.empty()) {
31                // Use the first odd-occurring digit as the middle character
32                middle = digit;
33                digitCount[digit] -= 1;
34            }
35        }
36
37        // Reverse the first half and concatenate with the middle and first half to form the palindrome
38        std::string reversedHalf = halfPalindrome;
39        std::reverse(reversedHalf.begin(), reversedHalf.end());
40        std::string palindrome = halfPalindrome + middle + reversedHalf;
41
42        // If after forming the palindrome, it is empty or only zeros, return '0'
43        if (palindrome.empty() || palindrome.find_first_not_of('0') == std::string::npos) {
44            return "0";
45        } else {
46            return palindrome;
47        }
48    }
49};
50
1function largestPalindromic(num: string): string {
2    // Create a counter for the digits in the input string
3    const digitCount: { [key: string]: number } = {};
4    for (const c of num) {
5        digitCount[c] = (digitCount[c] || 0) + 1;
6    }
7
8    // Initialize the middle character of the palindrome as empty
9    let middle = "";
10    // Initialize the first half of the palindrome as empty
11    let halfPalindrome = "";
12
13    // Loop from the largest digit to the smallest to construct the first half of the palindrome
14    for (let digit = 9; digit >= 0; digit--) {
15        const char = digit.toString();
16        if (digitCount[char] > 1) {
17            // Add half of the even occurrences of the digit to the first half of the palindrome
18            // Only add non-zero digits or zero digits if other digits are already in the halfPalindrome
19            if (char !== '0' || (char === '0' && halfPalindrome.length > 0)) {
20                halfPalindrome += char.repeat(Math.floor(digitCount[char] / 2));
21            }
22            // Leave any odd occurrence for potential use in the middle
23            digitCount[char] %= 2;
24        }
25        if (digitCount[char] === 1 && middle === "") {
26            // Use the first odd-occurring digit as the middle character
27            middle = char;
28            digitCount[char] -= 1;
29        }
30    }
31
32    // Reverse the first half and concatenate with the middle and first half to form the palindrome
33    const palindrome = halfPalindrome + middle + [...halfPalindrome].reverse().join('');
34
35    // If after forming the palindrome, it is empty or only zeros, return '0'
36    return palindrome.length === 0 || parseInt(palindrome) === 0 ? "0" : palindrome;
37}
38
39console.log(largestPalindromic("00009")); // Output: "9"
40
Not Sure What to Study? Take the 2-min Quiz：

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Time and Space Complexity

The given code snippet aims to find the largest palindromic number that can be formed by rearranging the digits of the given number num. The code uses a Counter to store the frequency of each digit and then constructs the palindrome.

  • Time Complexity:

    The time complexity of the code is determined by a few operations:

    1. Creating a Counter from the string num takes O(n) where n is the length of num, as each character in the string needs to be read once.
    2. The first loop runs a constant 10 times (digits 9 to 0) which is O(1) since it doesn't depend on the length of num.
    3. The second loop also runs a constant 10 times, and inside this loop, it performs string concatenation. Assuming that the Python string concatenation in this case takes O(k) time (where k is the length of the string being concatenated), the maximum length of s will be n/2. Therefore, the overall work done here is proportional to n.

    Since these operations occur sequentially, the time complexity is the sum of their individual complexities, resulting in O(n).

  • Space Complexity:

    The space complexity is determined by:

    1. The Counter cnt, which can potentially store a count for each different digit, thus having a space complexity of O(10) or O(1) since the number of possible different digits (0-9) is constant and does not grow with n.
    2. The string ans, which can grow up to a length of n in the worst case when each character is identical. Thus it has a space complexity of O(n).

    Therefore, the total space complexity is O(n), where n is the length of the input number num.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Depth first search is equivalent to which of the tree traversal order?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫