Jobs

Interviews

Discussions

Next Palindrome Using Same Digits

Hard

Asked by:

16 views

Topics:

StringsArraysGreedy Algorithms

You are given a numeric string num, representing a large integer. Return the string representing the next greater palindrome larger than num using the same digits. If there is no next greater palindrome, return an empty string "".

A palindrome is a number that reads the same backward as forward.

Example 1:

Input: num = "1221"
Output: "2112"
Explanation: The next greater palindrome using the same digits is "2112".

Example 2:

Input: num = "32123"
Output: "32223"
Explanation: The next greater palindrome using the same digits is "32223".

Example 3:

Input: num = "45545"
Output: "54545"
Explanation: The next greater palindrome using the same digits is "54545".

Constraints:

1 <= num.length <= 10⁵
num consists of digits.
num does not have leading zeros.

Try coding it in LeetCode

Next Palindrome Using Same Digits

Hard

Asked by:

16 views

Topics:

StringsArraysGreedy Algorithms

A palindrome is a number that reads the same backward as forward.

Example 1:

Input: num = "1221"
Output: "2112"
Explanation: The next greater palindrome using the same digits is "2112".

Example 2:

Input: num = "32123"
Output: "32223"
Explanation: The next greater palindrome using the same digits is "32223".

Example 3:

Input: num = "45545"
Output: "54545"
Explanation: The next greater palindrome using the same digits is "54545".

Constraints:

1 <= num.length <= 10⁵
num consists of digits.
num does not have leading zeros.

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 expected return value if the input number already represents the largest possible palindrome that can be formed using the given digits?
Are we guaranteed that the input will only contain digits, or do we need to handle cases with non-digit characters?
If the input is a palindrome to begin with, should I find the *next* largest palindrome, or return the original input?
Are leading zeros allowed in the input, and if so, should the next palindrome also allow leading zeros?
What is the maximum number of digits the input number can have?

Brute Force Solution

Approach

To find the next palindrome using the same digits, the brute force method is like trying every possible arrangement of those digits. We check each arrangement to see if it is a palindrome and if it is larger than the original number.

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

First, generate all possible numbers you can make using the given digits. Think of this as shuffling the digits around in every possible order.
Next, for each of these numbers, check two things. First, see if it reads the same forwards and backward to determine if it's a palindrome.
Second, check if it's larger than the original number we started with.
If a number satisfies both conditions (it's a palindrome and it's larger than the original), keep it in mind.
After checking all possible numbers, find the smallest one among those that met both conditions. That's the next palindrome.

Code Implementation

from itertools import permutations

def find_next_palindrome_brute_force(number):
    number_string = str(number)
    digits = list(number_string)
    all_permutations = set(int("".join(permutation)) for permutation in permutations(digits))

    next_palindromes = []
    for possible_palindrome in all_permutations:

        # Eliminate any number smaller than or equal to original
        if possible_palindrome <= number:
            continue

        possible_palindrome_string = str(possible_palindrome)

        # Check if it is a palindrome
        if possible_palindrome_string == possible_palindrome_string[::-1]:
            next_palindromes.append(possible_palindrome)

    # Find the smallest of all palindromes
    if next_palindromes:
        return min(next_palindromes)
    else:
        return -1

Big(O) Analysis

Time Complexity

O(n! * n) – The approach involves generating all permutations of the input digits. For an input of n digits, there are n! (n factorial) possible permutations. For each permutation, we perform a palindrome check which takes O(n) time, comparing the digits from the start and end towards the middle. Thus, the overall time complexity is O(n! * n).

Space Complexity

O(N!) – The algorithm generates all possible permutations of the input digits, which can require storing up to N! permutations in the worst case (where N is the number of digits). Each permutation requires storing N digits. Thus, the space required to store all generated numbers becomes a significant contributor to space complexity. The space to check if each number is a palindrome takes O(N) space, but because N! numbers will be generated, and stored (before it is determined to be a palindrome or not), the total space complexity is O(N!).

Optimal Solution

Approach

The goal is to find the next largest palindrome using the same digits as the input. We want to avoid checking every possibility. The optimal approach smartly modifies the input number from the middle outwards to create the next palindrome if one exists.

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

First, divide the number into two halves (left and right) and handle the middle digit if the number has an odd number of digits.
Look at the left half and try to find a spot to make a small change that increases the number.
Specifically, start looking from the rightmost digit of the left half and find the first digit that's smaller than the digit to its right.
If you find such a digit, find the smallest digit to its right that's bigger than it, and swap them.
After the swap, sort the digits to the right of the swapped digit in ascending order to make the number as small as possible after the swap.
Now, create the right half of the palindrome by mirroring the new left half. If the original number had a middle digit, keep it.
If you can't find a place to make a change in the left half (meaning the digits are in descending order), it means there's no next palindrome possible with these digits. You would need to return an error or a special value indicating that.

Code Implementation

def next_palindrome(number_string):
    number_list = list(number_string)
    number_length = len(number_list)
    middle_index = number_length // 2
    left_half = number_list[:middle_index]
    right_half = number_list[number_length - middle_index:]
    odd_length = number_length % 2 != 0

    # Find the pivot point in the left half
    pivot_index = -1
    for i in range(len(left_half) - 2, -1, -1):
        if left_half[i] < left_half[i + 1]:
            pivot_index = i
            break

    if pivot_index == -1:
        return "Not Possible"

    # Find the swap element
    swap_index = -1
    for i in range(len(left_half) - 1, pivot_index, -1):
        if left_half[i] > left_half[pivot_index]:
            swap_index = i
            break

    # Swap the elements to increase the left half.
    left_half[pivot_index], left_half[swap_index] = left_half[swap_index], left_half[pivot_index]

    # Sort the right part of the left half to minimize the change.
    left_half[pivot_index + 1:] = sorted(left_half[pivot_index + 1:])

    new_left_half = left_half

    # Mirror the left half to create the palindrome.
    right_half = new_left_half[::-1]

    if odd_length:
        return ''.join(new_left_half) + number_list[middle_index] + ''.join(right_half)
    else:
        return ''.join(new_left_half) + ''.join(right_half)

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm iterates through the left half of the input number, which has a length of approximately n/2. Within this loop, the most expensive operation is sorting the digits to the right of the swapped digit. Since sorting takes O(k log k) time where k is the number of digits to sort, and in the worst case k can be proportional to n, sorting will take O(n log n) time. Because this occurs within a loop that is O(n), this would be O(n^2 log n). However, since the sort only happens once, the complexity is just dominated by n log n. Therefore, the overall time complexity is O(n log n).

Space Complexity

O(N) – The auxiliary space is primarily determined by the need to store a modified version of the left half of the input number's digits. The sorting operation in step 5 creates a copy that, in the worst case, might involve all digits to the right of the swapped digit which can approach the size of N/2, where N is the number of digits in the input number. The space for mirroring the left half to construct the right half contributes another N/2 in the worst case. Thus the space complexity is proportional to N which is O(N).

Edge Cases

Case	How to Handle
Null or empty input string	Return null or empty string, indicating no palindrome can be formed.
Input string contains non-numeric characters	Reject the input and throw an IllegalArgumentException or return an error code.
Input string with odd length and all digits are the same (e.g., '111')	Check if a swap is possible, and if not, return the input string as there's no next palindrome, or return an error.
Input that can form no palindrome (e.g., odd counts for more than one digit)	Detect unsuitability for palindrome creation and return an appropriate error or null.
Input results in integer overflow when constructing the palindrome	Check the length of the input string and potential size of the result to avoid overflow errors and use appropriate data structures (e.g., String or BigInteger).
Input is already the largest possible palindrome with the given digits	If no larger permutation exists, return the input string or an indicator that a next palindrome is not possible.
Input string with only zeros (e.g., '000')	If only zeros are present, it may result in leading zeros; handle leading zeros properly or return a string representing zero only if no other palindrome can be constructed.
Input length greater than reasonable limits, affecting time complexity significantly.	Handle potentially long inputs by checking the input string length and possibly throwing an exception for excessively large inputs to prevent resource exhaustion.

Null or empty input string

How to Handle:

Return null or empty string, indicating no palindrome can be formed.

Input string contains non-numeric characters

How to Handle:

Reject the input and throw an IllegalArgumentException or return an error code.

Input string with odd length and all digits are the same (e.g., '111')

How to Handle:

Check if a swap is possible, and if not, return the input string as there's no next palindrome, or return an error.

Input that can form no palindrome (e.g., odd counts for more than one digit)

How to Handle:

Detect unsuitability for palindrome creation and return an appropriate error or null.

Input results in integer overflow when constructing the palindrome

How to Handle:

Check the length of the input string and potential size of the result to avoid overflow errors and use appropriate data structures (e.g., String or BigInteger).

Input is already the largest possible palindrome with the given digits

How to Handle:

If no larger permutation exists, return the input string or an indicator that a next palindrome is not possible.

Input string with only zeros (e.g., '000')

How to Handle:

If only zeros are present, it may result in leading zeros; handle leading zeros properly or return a string representing zero only if no other palindrome can be constructed.

Input length greater than reasonable limits, affecting time complexity significantly.

How to Handle:

Handle potentially long inputs by checking the input string length and possibly throwing an exception for excessively large inputs to prevent resource exhaustion.

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 expected return value if the input number already represents the largest possible palindrome that can be formed using the given digits?
Are we guaranteed that the input will only contain digits, or do we need to handle cases with non-digit characters?
If the input is a palindrome to begin with, should I find the *next* largest palindrome, or return the original input?
Are leading zeros allowed in the input, and if so, should the next palindrome also allow leading zeros?
What is the maximum number of digits the input number can have?

Brute Force Solution

Approach

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

First, generate all possible numbers you can make using the given digits. Think of this as shuffling the digits around in every possible order.
Next, for each of these numbers, check two things. First, see if it reads the same forwards and backward to determine if it's a palindrome.
Second, check if it's larger than the original number we started with.
If a number satisfies both conditions (it's a palindrome and it's larger than the original), keep it in mind.
After checking all possible numbers, find the smallest one among those that met both conditions. That's the next palindrome.

Code Implementation

from itertools import permutations

def find_next_palindrome_brute_force(number):
    number_string = str(number)
    digits = list(number_string)
    all_permutations = set(int("".join(permutation)) for permutation in permutations(digits))

    next_palindromes = []
    for possible_palindrome in all_permutations:

        # Eliminate any number smaller than or equal to original
        if possible_palindrome <= number:
            continue

        possible_palindrome_string = str(possible_palindrome)

        # Check if it is a palindrome
        if possible_palindrome_string == possible_palindrome_string[::-1]:
            next_palindromes.append(possible_palindrome)

    # Find the smallest of all palindromes
    if next_palindromes:
        return min(next_palindromes)
    else:
        return -1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, divide the number into two halves (left and right) and handle the middle digit if the number has an odd number of digits.
Look at the left half and try to find a spot to make a small change that increases the number.
Specifically, start looking from the rightmost digit of the left half and find the first digit that's smaller than the digit to its right.
If you find such a digit, find the smallest digit to its right that's bigger than it, and swap them.
After the swap, sort the digits to the right of the swapped digit in ascending order to make the number as small as possible after the swap.
Now, create the right half of the palindrome by mirroring the new left half. If the original number had a middle digit, keep it.
If you can't find a place to make a change in the left half (meaning the digits are in descending order), it means there's no next palindrome possible with these digits. You would need to return an error or a special value indicating that.

Code Implementation

def next_palindrome(number_string):
    number_list = list(number_string)
    number_length = len(number_list)
    middle_index = number_length // 2
    left_half = number_list[:middle_index]
    right_half = number_list[number_length - middle_index:]
    odd_length = number_length % 2 != 0

    # Find the pivot point in the left half
    pivot_index = -1
    for i in range(len(left_half) - 2, -1, -1):
        if left_half[i] < left_half[i + 1]:
            pivot_index = i
            break

    if pivot_index == -1:
        return "Not Possible"

    # Find the swap element
    swap_index = -1
    for i in range(len(left_half) - 1, pivot_index, -1):
        if left_half[i] > left_half[pivot_index]:
            swap_index = i
            break

    # Swap the elements to increase the left half.
    left_half[pivot_index], left_half[swap_index] = left_half[swap_index], left_half[pivot_index]

    # Sort the right part of the left half to minimize the change.
    left_half[pivot_index + 1:] = sorted(left_half[pivot_index + 1:])

    new_left_half = left_half

    # Mirror the left half to create the palindrome.
    right_half = new_left_half[::-1]

    if odd_length:
        return ''.join(new_left_half) + number_list[middle_index] + ''.join(right_half)
    else:
        return ''.join(new_left_half) + ''.join(right_half)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return null or empty string, indicating no palindrome can be formed.
Input string contains non-numeric characters	Reject the input and throw an IllegalArgumentException or return an error code.
Input string with odd length and all digits are the same (e.g., '111')	Check if a swap is possible, and if not, return the input string as there's no next palindrome, or return an error.
Input that can form no palindrome (e.g., odd counts for more than one digit)	Detect unsuitability for palindrome creation and return an appropriate error or null.
Input results in integer overflow when constructing the palindrome	Check the length of the input string and potential size of the result to avoid overflow errors and use appropriate data structures (e.g., String or BigInteger).
Input is already the largest possible palindrome with the given digits	If no larger permutation exists, return the input string or an indicator that a next palindrome is not possible.
Input string with only zeros (e.g., '000')	If only zeros are present, it may result in leading zeros; handle leading zeros properly or return a string representing zero only if no other palindrome can be constructed.
Input length greater than reasonable limits, affecting time complexity significantly.	Handle potentially long inputs by checking the input string length and possibly throwing an exception for excessively large inputs to prevent resource exhaustion.

Null or empty input string

How to Handle:

Return null or empty string, indicating no palindrome can be formed.

Input string contains non-numeric characters

How to Handle:

Reject the input and throw an IllegalArgumentException or return an error code.

Input string with odd length and all digits are the same (e.g., '111')

How to Handle:

Check if a swap is possible, and if not, return the input string as there's no next palindrome, or return an error.

Input that can form no palindrome (e.g., odd counts for more than one digit)

How to Handle:

Detect unsuitability for palindrome creation and return an appropriate error or null.

Input results in integer overflow when constructing the palindrome

How to Handle:

Check the length of the input string and potential size of the result to avoid overflow errors and use appropriate data structures (e.g., String or BigInteger).

Input is already the largest possible palindrome with the given digits

How to Handle:

If no larger permutation exists, return the input string or an indicator that a next palindrome is not possible.

Input string with only zeros (e.g., '000')

How to Handle:

If only zeros are present, it may result in leading zeros; handle leading zeros properly or return a string representing zero only if no other palindrome can be constructed.

Input length greater than reasonable limits, affecting time complexity significantly.

How to Handle:

Handle potentially long inputs by checking the input string length and possibly throwing an exception for excessively large inputs to prevent resource exhaustion.