We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Next Palindrome Using Same Digits

Number: 1997

Difficulty: Hard

Paid? Yes

Companies: Amazon

Problem Description

You are given a numeric string num, representing a very large palindrome. The task is to return the smallest palindrome larger than num that can be created by rearranging its digits. If no such palindrome exists, return an empty string.

Key Insights

  • Since num is originally a palindrome, its digit frequency permits a palindrome arrangement.
  • For even-length palindromes, the full number is determined by its first half and its mirrored second half.
  • For odd-length palindromes, aside from the center digit (which remains fixed because it is the unique odd-count element), the number is determined by the first half; the second half is the mirror of the first.
  • The problem reduces to finding the next lexicographical permutation of the first half.
  • If the next permutation of the half does not exist (i.e. it is sorted in descending order), it is impossible to form a larger palindrome using these digits.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the input string; the next permutation algorithm and palindrome construction both traverse at most half of the digits. Space Complexity: O(n) to store and manipulate the half and the final palindrome string.

Solution

The strategy is to extract the first half of the palindrome. For even-length numbers, the first half is simply the first n/2 digits. For odd-length numbers, the center digit remains fixed and we only work with the first floor(n/2) digits. Using the next permutation algorithm (a standard method used to generate the next lexicographical permutation), we try to update the first half to its next higher order. If a next permutation exists, we construct the new palindrome by combining the updated half, the center (if it exists), and the reverse of the updated half. If the next permutation is not possible, then there is no feasible larger palindrome that can be formed by rearranging the digits.

Key details:

  • Use the standard next-permutation method: from the right side, find the first digit that is smaller than its neighbor, then swap it with the smallest digit on its right that is larger than it, and finally reverse the segment after the pivot.
  • Mirror the obtained half (and include the center digit for odd-length strings) to get the complete new palindrome.

Code Solutions

# Python solution with line-by-line comments

def next_palindrome(num: str) -> str:
    n = len(num)
    half_len = n // 2  # For even, half is n/2; for odd, center remains fixed
    first_half = list(num[:half_len])
    center = num[half_len] if n % 2 else ""
    
    # Function to compute next permutation for a list of characters (digits)
    def next_permutation(arr):
        # Step 1: find the rightmost index 'i' such that arr[i] < arr[i+1]
        i = len(arr) - 2
        while i >= 0 and arr[i] >= arr[i + 1]:
            i -= 1
        if i < 0:
            return False  # next permutation does not exist
        # Step 2: find the rightmost index 'j' such that arr[j] > arr[i]
        j = len(arr) - 1
        while arr[j] <= arr[i]:
            j -= 1
        # Step 3: swap arr[i] and arr[j]
        arr[i], arr[j] = arr[j], arr[i]
        # Step 4: reverse the sub-array arr[i+1:]
        arr[i+1:] = reversed(arr[i+1:])
        return True

    # If next permutation for the first half exists, then use it to build the new palindrome.
    if next_permutation(first_half):
        new_half = "".join(first_half)
        # The new palindrome is new_half + center (if odd length) + reversed new_half.
        return new_half + center + new_half[::-1]
    else:
        # No next permutation can be found; return empty string.
        return ""

# Example usage:
#print(next_palindrome("1221"))      # Expected output: "2112"
#print(next_palindrome("32123"))     # Expected output: ""
#print(next_palindrome("45544554"))  # Expected output: "54455445"
← Back to All Questions