201. Next Larger Palindrome Using Same Digits

Next Larger Palindrome Using Same Digits

You are given a numeric string num.

The string num represents a very large palindrome.

Return the smallest palindrome that is strictly larger than num and can be formed by rearranging exactly the same digits.

If it is not possible to form any larger palindrome using the same digits, return an empty string "".

A palindrome is a number that reads the same from left to right and from right to left.

Class Definition

Implement the class NextPalindromeUsingSameDigits.

Constructor

NextPalindromeUsingSameDigits()

Initializes an object of the class.

Method

String nextPalindrome(String num)

Returns the smallest palindrome that is larger than num and can be created by rearranging the digits of num.

If no such palindrome exists, return "".

Deterministic Output Rule

If multiple larger palindromes can be created from the same digits, return the numerically smallest one among them.

This makes the output deterministic.

Input Representation

The input number is given as a string because it may be very large.

The string contains only digit characters from '0' to '9'.

Constraints

1 ≤ num.length ≤ 100,000
num contains only digits.
num is a palindrome.
num does not need to fit inside any integer data type.
The returned string must use exactly the same digits as num.
The returned string must be strictly larger than num.

Examples

Example 1

Method call:
nextPalindrome(num = "1331")

Output:
"3113"

Explanation:
The digits can be rearranged to form "3113", which is a palindrome larger than "1331". It is also the smallest such larger palindrome.

Example 2

Method call:
nextPalindrome(num = "987789")

Output:
""

Explanation:
The left half "987" is already in descending order, so no larger palindrome can be formed using the same digits.

Example 3

Method call:
nextPalindrome(num = "1441")

Output:
"4114"

Explanation:
The next larger arrangement of the left half "14" is "41". Mirroring it gives "4114".

Example 4

Method call:
nextPalindrome(num = "23532")

Output:
"32523"

Explanation:
The middle digit remains unchanged. The next larger arrangement of the left half "23" is "32", and mirroring it around the middle digit gives "32523".

Example 5

Method call:
nextPalindrome(num = "543345")

Output:
""

Explanation:
The left half "543" has no next lexicographically larger permutation. Therefore, no strictly larger palindrome can be formed using the same digits.