Jobs

Interviews

Discussions

Largest Palindromic Number

Medium

Asked by:

6 views

Topics:

ArraysGreedy AlgorithmsStrings

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 "444947137" 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 <= 10⁵
num consists of digits.

Try coding it in LeetCode

Largest Palindromic Number

Medium

Asked by:

6 views

Topics:

ArraysGreedy AlgorithmsStrings

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 "444947137" 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 <= 10⁵
num consists of digits.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string `num`?
Can the input string `num` contain any characters other than digits?
If no palindrome can be formed from the digits in `num`, should I return "0" or an empty string?
If a palindrome can be formed, but it results in a number with leading zeros, should I still return "0" even if non-zero digits exist?
Are there any memory constraints I should be aware of, considering the potentially large size of the input?

Brute Force Solution

Approach

The goal is to find the biggest palindrome we can create using digits from a given number. The brute force method tries every possible combination of digits to see if it forms a palindrome and then picks the largest one.

Here's how the algorithm would work step-by-step:

Consider all possible subsequences of the given number's digits.
For each subsequence, check if it is a palindrome.
If a subsequence is a palindrome, save it.
After checking all subsequences, compare all the saved palindromes.
The largest palindrome found is the answer.

Code Implementation

def largest_palindrome_brute_force(digits):
    largest_palindrome_found = ""
    digits_length = len(digits)

    for start_index in range(digits_length):
        for end_index in range(digits_length, start_index, -1):
            substring = digits[start_index:end_index]

            # Check if the substring is a palindrome
            if substring == substring[::-1]:

                # Update if current substring is larger
                if len(substring) > len(largest_palindrome_found):
                    largest_palindrome_found = substring
                elif len(substring) == len(largest_palindrome_found) and substring > largest_palindrome_found:
                    largest_palindrome_found = substring

    # Need to handle empty string case to return '0' if no palindromes were found
    if not largest_palindrome_found:
        return '0'
    
    return largest_palindrome_found

Big(O) Analysis

Time Complexity

O(2^n * n) – The algorithm considers all possible subsequences of the input number. A number of length n has 2^n subsequences. For each subsequence, it checks if the subsequence is a palindrome, which takes O(n) time in the worst case (comparing the first and last characters, and moving inwards). Therefore, the total time complexity is O(2^n * n).

Space Complexity

O(2^N) – The algorithm considers all possible subsequences of the given number's digits. In the worst-case scenario, the number of subsequences can be 2^N, where N is the number of digits in the input number. Each generated subsequence, potentially of length up to N, is stored to check if it is a palindrome, leading to a space complexity proportional to the number of subsequences. Further, saving all palindromes found contributes an auxiliary space proportional to the number of palindromic subsequences. Therefore, the overall space complexity is dominated by the storage of all possible subsequences, approximately O(2^N).

Optimal Solution

Approach

The best way to solve this is to build the largest possible palindrome digit by digit. We achieve this by greedily using the largest digit pairs available and placing them on either end of our result. We only need to handle a possible middle digit as a special case.

Here's how the algorithm would work step-by-step:

Count how many times each digit appears in the input number.
Start building the palindrome from the outside in. For each digit from 9 down to 1, take pairs of that digit and put one at the beginning and one at the end of our palindrome. This uses the largest digits first and builds the longest possible palindromic structure.
If the digit 0 is present, and it is the only digit we use, return '0'.
If after forming pairs, there are any digits left over, find the largest of these single digits. Put that digit in the very middle of our palindrome. If there is no remaining digit, the palindrome is complete.
If the built palindromic number is empty at the end, return '0'. This handles the case where we had zero digits and single zero case.
Combine the left half, the optional middle digit, and the reversed left half to form the largest palindromic number.

Code Implementation

def largest_palindromic_number(number):
    digit_counts = {}
    for digit in number:
        digit_counts[digit] = digit_counts.get(digit, 0) + 1

    first_half = ""
    middle_digit = ""

    # Build the first half of the palindrome.
    for digit in range(9, -1, -1):
        digit_string = str(digit)
        count = digit_counts.get(digit_string, 0)
        first_half += digit_string * (count // 2)

    # Find the largest digit that appears an odd number of times.
    for digit in range(9, -1, -1):
        digit_string = str(digit)
        count = digit_counts.get(digit_string, 0)
        if count % 2 == 1:
            middle_digit = digit_string
            break

    second_half = first_half[::-1]
    palindrome = first_half + middle_digit + second_half

    # Remove leading zeros, but keep a single zero if the result is all zeros.
    palindrome = palindrome.lstrip('0')

    if not palindrome:
        return "0"

    return palindrome

Big(O) Analysis

Time Complexity

O(n) – The algorithm first counts the occurrences of each digit (0-9) in the input number of length n. This takes O(n) time. Then, it iterates through the digits 9 to 0, which is a constant time operation (O(1)). Within this loop, the algorithm might append digits to the beginning and end of the palindrome string, with the number of appends being bounded by n. The final steps involve at most a single reverse operation on a string of length at most n. Therefore, the dominant operation is counting the digits which takes O(n) time. The overall time complexity is thus O(n).

Space Complexity

O(1) – The algorithm primarily uses a digit count array of size 10 to store the frequency of each digit (0-9), and a few string variables to build the palindromic number. The size of the digit count array is constant, independent of the input number's size (N). Although the result string grows as the palindrome is being constructed, the plain English description does not explicitly state that we store the left half of the palindromic string for later concatenation, allowing us to do the palindrome construction with in-place string manipulation or a string builder (often optimized by compilers). Thus, the auxiliary space remains constant.

Edge Cases

Case	How to Handle
Input string `num` is null or empty.	Return '0' immediately since no palindrome can be constructed.
Input string `num` contains only the digit '0'.	If after processing, only '0's remain, return '0' to avoid leading zeros or return the maximal '0' string if it yields a non-empty result.
Input string `num` contains only a single digit other than zero.	Return the single digit as it is a palindrome.
Input string `num` contains an odd number of one or more digits.	The middle digit should be the largest single digit with an odd count.
Input string `num` contains a large number of digits potentially causing memory issues if not handled efficiently.	Use a frequency map to store the counts of digits to avoid storing a large number of digits directly.
Input `num` has all even counts of digits but contains leading zeros after palindrome construction.	Remove leading zeros from the result, but if the result becomes empty after removing leading zeros, return '0'.
Input `num` such that only '0's can form the palindrome body.	If the largest palindrome contains only '0' digits, return "0" instead of potentially numerous leading zeros.
Input contains only '0's in even counts and a '1' in odd count.	Return '1' if no digits are greater than 0 when constructing the prefix.

Input string `num` is null or empty.

How to Handle:

Return '0' immediately since no palindrome can be constructed.

Input string `num` contains only the digit '0'.

How to Handle:

If after processing, only '0's remain, return '0' to avoid leading zeros or return the maximal '0' string if it yields a non-empty result.

Input string `num` contains only a single digit other than zero.

How to Handle:

Return the single digit as it is a palindrome.

Input string `num` contains an odd number of one or more digits.

How to Handle:

The middle digit should be the largest single digit with an odd count.

Input string `num` contains a large number of digits potentially causing memory issues if not handled efficiently.

How to Handle:

Use a frequency map to store the counts of digits to avoid storing a large number of digits directly.

Input `num` has all even counts of digits but contains leading zeros after palindrome construction.

How to Handle:

Remove leading zeros from the result, but if the result becomes empty after removing leading zeros, return '0'.

Input `num` such that only '0's can form the palindrome body.

How to Handle:

If the largest palindrome contains only '0' digits, return "0" instead of potentially numerous leading zeros.

Input contains only '0's in even counts and a '1' in odd count.

How to Handle:

Return '1' if no digits are greater than 0 when constructing the prefix.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string `num`?
Can the input string `num` contain any characters other than digits?
If no palindrome can be formed from the digits in `num`, should I return "0" or an empty string?
If a palindrome can be formed, but it results in a number with leading zeros, should I still return "0" even if non-zero digits exist?
Are there any memory constraints I should be aware of, considering the potentially large size of the input?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider all possible subsequences of the given number's digits.
For each subsequence, check if it is a palindrome.
If a subsequence is a palindrome, save it.
After checking all subsequences, compare all the saved palindromes.
The largest palindrome found is the answer.

Code Implementation

def largest_palindrome_brute_force(digits):
    largest_palindrome_found = ""
    digits_length = len(digits)

    for start_index in range(digits_length):
        for end_index in range(digits_length, start_index, -1):
            substring = digits[start_index:end_index]

            # Check if the substring is a palindrome
            if substring == substring[::-1]:

                # Update if current substring is larger
                if len(substring) > len(largest_palindrome_found):
                    largest_palindrome_found = substring
                elif len(substring) == len(largest_palindrome_found) and substring > largest_palindrome_found:
                    largest_palindrome_found = substring

    # Need to handle empty string case to return '0' if no palindromes were found
    if not largest_palindrome_found:
        return '0'
    
    return largest_palindrome_found

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Count how many times each digit appears in the input number.
Start building the palindrome from the outside in. For each digit from 9 down to 1, take pairs of that digit and put one at the beginning and one at the end of our palindrome. This uses the largest digits first and builds the longest possible palindromic structure.
If the digit 0 is present, and it is the only digit we use, return '0'.
If after forming pairs, there are any digits left over, find the largest of these single digits. Put that digit in the very middle of our palindrome. If there is no remaining digit, the palindrome is complete.
If the built palindromic number is empty at the end, return '0'. This handles the case where we had zero digits and single zero case.
Combine the left half, the optional middle digit, and the reversed left half to form the largest palindromic number.

Code Implementation

def largest_palindromic_number(number):
    digit_counts = {}
    for digit in number:
        digit_counts[digit] = digit_counts.get(digit, 0) + 1

    first_half = ""
    middle_digit = ""

    # Build the first half of the palindrome.
    for digit in range(9, -1, -1):
        digit_string = str(digit)
        count = digit_counts.get(digit_string, 0)
        first_half += digit_string * (count // 2)

    # Find the largest digit that appears an odd number of times.
    for digit in range(9, -1, -1):
        digit_string = str(digit)
        count = digit_counts.get(digit_string, 0)
        if count % 2 == 1:
            middle_digit = digit_string
            break

    second_half = first_half[::-1]
    palindrome = first_half + middle_digit + second_half

    # Remove leading zeros, but keep a single zero if the result is all zeros.
    palindrome = palindrome.lstrip('0')

    if not palindrome:
        return "0"

    return palindrome

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input string `num` is null or empty.	Return '0' immediately since no palindrome can be constructed.
Input string `num` contains only the digit '0'.	If after processing, only '0's remain, return '0' to avoid leading zeros or return the maximal '0' string if it yields a non-empty result.
Input string `num` contains only a single digit other than zero.	Return the single digit as it is a palindrome.
Input string `num` contains an odd number of one or more digits.	The middle digit should be the largest single digit with an odd count.
Input string `num` contains a large number of digits potentially causing memory issues if not handled efficiently.	Use a frequency map to store the counts of digits to avoid storing a large number of digits directly.
Input `num` has all even counts of digits but contains leading zeros after palindrome construction.	Remove leading zeros from the result, but if the result becomes empty after removing leading zeros, return '0'.
Input `num` such that only '0's can form the palindrome body.	If the largest palindrome contains only '0' digits, return "0" instead of potentially numerous leading zeros.
Input contains only '0's in even counts and a '1' in odd count.	Return '1' if no digits are greater than 0 when constructing the prefix.

Input string `num` is null or empty.

How to Handle:

Return '0' immediately since no palindrome can be constructed.

Input string `num` contains only the digit '0'.

How to Handle:

If after processing, only '0's remain, return '0' to avoid leading zeros or return the maximal '0' string if it yields a non-empty result.

Input string `num` contains only a single digit other than zero.

How to Handle:

Return the single digit as it is a palindrome.

Input string `num` contains an odd number of one or more digits.

How to Handle:

The middle digit should be the largest single digit with an odd count.

Input string `num` contains a large number of digits potentially causing memory issues if not handled efficiently.

How to Handle:

Use a frequency map to store the counts of digits to avoid storing a large number of digits directly.

Input `num` has all even counts of digits but contains leading zeros after palindrome construction.

How to Handle:

Remove leading zeros from the result, but if the result becomes empty after removing leading zeros, return '0'.

Input `num` such that only '0's can form the palindrome body.

How to Handle:

If the largest palindrome contains only '0' digits, return "0" instead of potentially numerous leading zeros.

Input contains only '0's in even counts and a '1' in odd count.

How to Handle:

Return '1' if no digits are greater than 0 when constructing the prefix.