Next Mirror Number

Hard

You get a string digits holding a huge palindromic number (it reads the same left to right and right to left). Rearrange its digits into another palindrome: the smallest one that is strictly greater than the original number. Return it as a string. If there is no such palindrome, return the empty string.

Example 1

digits='3443' → '4334'

The digits 3, 3, 4, 4 form the palindromes 3443 and 4334; the next one after 3443 is 4334.

Example 2

digits='97179' → ''

The middle 1 has to stay put, and the left half "97" cannot be made larger by reordering, so the answer is the empty string.

Example 3

digits='1235321' → '1325231'

The left half "123" becomes its next arrangement "132", and the number is mirrored: 1325231.

Constraints

1 ≤ len(digits) ≤ 10⁵
digits consists of digits and is a palindrome

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Two Pointers String

Similar problems

Mirror Chunk Split Hard Alphabetically Last Piece Hard Palindrome by Adjacent Swaps Hard Disjoint Long Palindromes Hard Cheapest Cut to a Subsequence Hard

Input

digits='3443'

Expected

'4334'

Run checks the first 3 tests in your browser. Submit checks all 121 tests on the server, hidden ones included.