LeetCode 1842 - Next Palindrome Using Same Digits

The input is a numeric string num that is guaranteed to already be a palindrome. The task is to rearrange its digits to create another palindrome that is strictly larger than the original number, while also being the smallest such palindrome possible.

leetcodehardtwo-pointersstring

LeetCode Problem 1842

Difficulty: 🔴 Hard
Topics: Two Pointers, String

Solution

Problem Understanding

The input is a numeric string num that is guaranteed to already be a palindrome. The task is to rearrange its digits to create another palindrome that is strictly larger than the original number, while also being the smallest such palindrome possible.

A palindrome has mirror symmetry. For example:

  • "1221" is a palindrome because it reads the same from left to right and right to left.
  • "45544554" is also a palindrome.

The important observation is that once the left half of a palindrome is fixed, the right half is automatically determined. For example:

  • Left half "12" produces palindrome "1221"
  • Left half "54" produces palindrome "5445"

For odd length palindromes, the middle digit stays fixed while the two halves mirror each other:

  • Left half "32" with middle digit "1" produces "32123"

The problem is essentially asking:

Find the next lexicographically larger arrangement of the first half of the palindrome, then mirror it to form the smallest larger palindrome.

The constraints are extremely important:

  • num.length can be up to 10^5
  • This rules out generating permutations
  • Any factorial or exponential approach is impossible
  • Even quadratic solutions may be too slow

This means we need a linear or near linear algorithm.

Several edge cases are important:

  • A palindrome may already use the largest possible arrangement of its left half, meaning no larger palindrome exists
  • Single digit inputs cannot produce another palindrome
  • Repeated digits can complicate next permutation logic
  • Odd and even length palindromes behave slightly differently because of the center digit

For example:

  • "32123" has left half "32", which is already the highest permutation, so the answer is ""
  • "9" also returns ""
  • "1221" becomes "2112" because the next permutation of "12" is "21"

Approaches

Brute Force Approach

A brute force solution would generate every permutation of the digits, filter the permutations that form valid palindromes, sort them, and then locate the next larger palindrome.

This approach is correct because it explicitly checks all possible rearrangements and selects the smallest valid palindrome greater than the original number.

However, this is completely impractical.

If the length of the string is n, there can be up to n! permutations. Even with pruning and duplicate elimination, the number of possible permutations becomes astronomically large for n = 10^5.

The brute force approach is therefore unusable.

Optimal Approach

The key insight is that a palindrome is entirely determined by its first half.

Suppose the palindrome has length n.

  • The left half consists of the first n // 2 digits
  • The right half is simply the reverse of the left half
  • If n is odd, the middle digit remains unchanged

Therefore, instead of searching among all palindromes, we only need to find the next lexicographical permutation of the left half.

Once we obtain the next larger arrangement of the left half:

  • Mirror it
  • Reattach the middle digit if necessary
  • Construct the new palindrome

This works because lexicographical order on the left half directly determines lexicographical order of the full palindrome.

The problem therefore reduces to the classic "next permutation" problem.

Approach Time Complexity Space Complexity Notes
Brute Force O(n!) O(n!) Generates all permutations and filters palindromes
Optimal O(n) O(n) Finds next permutation of left half and mirrors it

Algorithm Walkthrough

  1. Determine the length of the string and extract the left half.

If n = len(num), then:

  • Left half is num[:n // 2]
  • Middle digit exists only when n is odd

Example:

  • "1221" → left half "12"
  • "32123" → left half "32", middle digit "1"
  1. Convert the left half into a mutable array.

Strings are immutable in both Python and Go, so we use an array or slice of characters for in place swapping and reversing. 3. Find the pivot for next permutation.

Starting from the end, locate the first index i such that:

arr[i] < arr[i + 1]

Everything to the right of this index is in descending order.

If no such index exists, the left half is already the largest possible permutation, so no larger palindrome exists. 4. Find the smallest digit larger than the pivot.

Starting again from the end, find the first index j such that:

arr[j] > arr[i]

Swap arr[i] and arr[j]. 5. Reverse the suffix after the pivot.

The suffix was previously in descending order.

Reversing it transforms it into ascending order, giving the smallest lexicographically larger permutation. 6. Construct the palindrome.

  • Convert the modified left half back into a string
  • Reverse it to form the mirrored right half
  • Insert the middle digit if the length is odd
  1. Return the constructed palindrome.

Why it works

The next permutation algorithm guarantees the smallest lexicographically larger arrangement of the left half.

Since a palindrome is uniquely determined by its left half and optional middle digit, the resulting mirrored palindrome is also the smallest palindrome strictly larger than the original number.

If no next permutation exists, then no larger palindrome can be formed from the digits.

Python Solution

class Solution:
    def nextPalindrome(self, num: str) -> str:
        n = len(num)

        if n == 1:
            return ""

        half_length = n // 2
        left_half = list(num[:half_length])

        # Step 1: Find pivot
        pivot = half_length - 2
        while pivot >= 0 and left_half[pivot] >= left_half[pivot + 1]:
            pivot -= 1

        # No next permutation exists
        if pivot < 0:
            return ""

        # Step 2: Find next larger element
        swap_index = half_length - 1
        while left_half[swap_index] <= left_half[pivot]:
            swap_index -= 1

        # Step 3: Swap
        left_half[pivot], left_half[swap_index] = (
            left_half[swap_index],
            left_half[pivot],
        )

        # Step 4: Reverse suffix
        left_half[pivot + 1:] = reversed(left_half[pivot + 1:])

        left = "".join(left_half)
        right = left[::-1]

        if n % 2 == 1:
            middle = num[half_length]
            return left + middle + right

        return left + right

The implementation follows the standard next permutation algorithm applied only to the left half of the palindrome.

The first section extracts the left half and handles the single digit edge case. A single digit cannot produce a larger palindrome using the same digits.

Next, the algorithm searches backward for the pivot index. This identifies the position where the sequence stops being non increasing.

If no pivot exists, the left half is already the maximum permutation, meaning no larger palindrome can be formed.

After locating the pivot, the code finds the smallest larger digit on the right side and swaps them. This ensures the increase is minimal.

The suffix reversal produces the smallest possible ordering after the pivot, guaranteeing the next lexicographical permutation rather than just any larger permutation.

Finally, the code mirrors the updated left half and inserts the middle digit if necessary.

Go Solution

package main

func nextPalindrome(num string) string {
	n := len(num)

	if n == 1 {
		return ""
	}

	halfLen := n / 2
	left := []byte(num[:halfLen])

	// Step 1: Find pivot
	pivot := halfLen - 2
	for pivot >= 0 && left[pivot] >= left[pivot+1] {
		pivot--
	}

	// No next permutation
	if pivot < 0 {
		return ""
	}

	// Step 2: Find next larger element
	swapIndex := halfLen - 1
	for left[swapIndex] <= left[pivot] {
		swapIndex--
	}

	// Step 3: Swap
	left[pivot], left[swapIndex] = left[swapIndex], left[pivot]

	// Step 4: Reverse suffix
	reverse(left[pivot+1:])

	leftStr := string(left)

	// Build reversed half
	right := reverseString(leftStr)

	if n%2 == 1 {
		middle := string(num[halfLen])
		return leftStr + middle + right
	}

	return leftStr + right
}

func reverse(arr []byte) {
	i, j := 0, len(arr)-1

	for i < j {
		arr[i], arr[j] = arr[j], arr[i]
		i++
		j--
	}
}

func reverseString(s string) string {
	bytes := []byte(s)

	i, j := 0, len(bytes)-1

	for i < j {
		bytes[i], bytes[j] = bytes[j], bytes[i]
		i++
		j--
	}

	return string(bytes)
}

The Go implementation mirrors the Python logic closely.

Because Go strings are immutable, the left half is converted into a []byte slice for efficient in place modifications.

The suffix reversal is implemented with a helper function operating directly on slices. Another helper reverses the final string to construct the mirrored half.

Unlike Python slicing, Go requires explicit helper functions for reversal operations.

Worked Examples

Example 1

Input:

num = "1221"

Left half:

"12"
Step State
Initial ['1', '2']
Find pivot 1 < 2, pivot = 0
Find swap index swap with '2'
After swap ['2', '1']
Reverse suffix unchanged
Final palindrome "2112"

Output:

"2112"

Example 2

Input:

num = "32123"

Left half:

"32"
Step State
Initial ['3', '2']
Find pivot no valid pivot
Result no next permutation

Output:

""

The left half is already the maximum permutation.

Example 3

Input:

num = "45544554"

Left half:

"4554"
Step State
Initial ['4', '5', '5', '4']
Pivot index 0
Swap index index 2
After swap ['5', '5', '4', '4']
Reverse suffix ['5', '4', '4', '5']
Final palindrome "54455445"

Output:

"54455445"

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each character is visited a constant number of times
Space O(n) Character arrays and result construction require linear space

The next permutation algorithm itself is linear because each scan traverses the half string at most once.

Constructing the final palindrome also requires linear time and space due to string creation and reversal.

Since only half the palindrome is processed directly, the actual operations are approximately proportional to n / 2, but asymptotically this remains O(n).

Test Cases

sol = Solution()

assert sol.nextPalindrome("1221") == "2112"  # basic even length case
assert sol.nextPalindrome("32123") == ""  # already maximum permutation
assert sol.nextPalindrome("45544554") == "54455445"  # repeated digits

assert sol.nextPalindrome("1") == ""  # single digit
assert sol.nextPalindrome("11") == ""  # identical digits only
assert sol.nextPalindrome("99999") == ""  # no larger permutation

assert sol.nextPalindrome("1001") == ""  # left half already descending
assert sol.nextPalindrome("2332") == "3223"  # simple swap

assert sol.nextPalindrome("3443") == "4334"  # even length repeated digits
assert sol.nextPalindrome("12321") == "21312"  # odd length case

assert sol.nextPalindrome("122221") == "212212"  # repeated middle structure
assert sol.nextPalindrome("469964") == "649946"  # multiple swaps possible

assert sol.nextPalindrome("543212345") == ""  # odd length no answer
assert sol.nextPalindrome("1110111") == ""  # all permutations identical

assert sol.nextPalindrome("125521") == "152251"  # suffix reversal needed
Test Why
"1221" Basic even length palindrome
"32123" No larger palindrome exists
"45544554" Handles repeated digits
"1" Smallest possible input
"11" All digits identical
"99999" Odd length with identical digits
"1001" Descending left half
"2332" Simple next permutation
"3443" Repeated digits in left half
"12321" Odd length palindrome
"122221" Complex mirrored structure
"469964" Multiple candidate swaps
"543212345" Maximum permutation already used
"1110111" No distinct larger arrangement
"125521" Requires suffix reversal

Edge Cases

Edge Case 1, Single Digit Input

A single digit number is already the only possible palindrome using that digit. There is no larger rearrangement.

For example:

"7"

The implementation immediately returns "" when n == 1.

Edge Case 2, Left Half Already Maximum

If the left half is already in descending order, no next permutation exists.

For example:

num = "32123"
left half = "32"

Since "32" is the largest permutation of those digits, there is no larger palindrome.

The pivot search fails and returns -1, causing the algorithm to return "".

Edge Case 3, Repeated Digits

Repeated digits can easily introduce bugs in next permutation implementations.

For example:

"45544554"

The algorithm must carefully choose the rightmost digit larger than the pivot and reverse the suffix correctly.

Using the standard next permutation procedure guarantees correctness even with duplicates.

Edge Case 4, Odd Length Palindromes

Odd length palindromes contain a middle digit that does not participate in permutation.

For example:

"12321"

Only the left half "12" changes. The middle digit "3" remains fixed.

The implementation preserves the middle digit exactly while mirroring the updated left half.