3646. Next Special Palindrome Number

Hard27.9% acceptance11,736 / 42,065 submissions

Asked by 1 company

You are given an integer n.

A number is called special if:

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:

Hint 1

There are only a few special numbers; preprocess them.

Hint 2

Use bitmasking to brute‑force all valid selections of digits k for the number.

Hint 3

Generate all permutations of the first half of the digits, then mirror them to form the full palindrome.

Hint 4

For each n, use binary search to find the smallest special number strictly greater than n.