3646. Next Special Palindrome Number
Description
You are given an integer n.
A number is called special if:
- It is a palindrome.
- Every digit
kin the number appears exactlyktimes.
Return the smallest special number strictly greater than n.
Example 1:
Input: n = 2
Output: 22
Explanation:
22 is the smallest special number greater than 2, as it is a palindrome and the digit 2 appears exactly 2 times.
Example 2:
Input: n = 33
Output: 212
Explanation:
212 is the smallest special number greater than 33, as it is a palindrome and the digits 1 and 2 appear exactly 1 and 2 times respectively.
Constraints:
0 <= n <= 1015
Solutions
Solution 1
Thinking
A special palindrome uses digit \(d\) exactly \(d\) times (under the stated frequency rule) and reads the same forwards. Checking \(n+1,n+2,\ldots\) fails for large \(n\).
Only finitely many multisets obey the frequencies. Enumerate half-permutations, mirror them, sort, and binary-search the successor of \(n\).
At most one odd-count digit sits in the center; the rest come in pairs. After generating every candidate, each query is the least value strictly above \(n\).
1 | |
1 | |
1 | |
1 | |