Next Palindrome with Exact Digit Counts

### Problem You are given a nonnegative integer `n`. A positive integer is special when both conditions hold in its ordinary decimal representation: - It reads the same from left to right and from right to left. - For each digit `d` that appears, the total number of occurrences of `d` is exactly `d`. Return the smallest special integer strictly greater than `n`. ```cpp class Solution { public: long long specialPalindrome(long long n); }; ``` ### Examples **Example 1:** ```text Input: n = 0 Output: 1 Explanation: The number 1 is a palindrome and contains its digit exactly once. It is the smallest positive integer greater than zero. ``` **Example 2:** ```text Input: n = 212 Output: 333 Explanation: The input itself is special but is excluded by the strict inequality. The number 333 is a palindrome containing three copies of digit 3, and no smaller special integer lies above 212. ``` ### Constraints - `0 <= n <= 10^15`. ### Clarifying Questions - Does the frequency rule apply to digits that do not appear? No; an absent digit need not be introduced. - Can a special number contain digit zero? No. An appearing zero would have to occur exactly zero times, which is impossible. - Is a palindrome with the right total length automatically special? No. Every appearing digit must meet its own exact count. - May the returned value equal `n` when `n` is special? No. It must be strictly greater. - Are leading zeros part of a number's representation? No. Use the ordinary decimal representation. ### What a Strong Answer Covers - Both palindrome symmetry and every exact digit-frequency condition. - The strict lower bound and why the returned valid integer is the smallest one above it. - Completeness and resource bounds for the entire allowed range of `n`. - Arithmetic that safely stores the result and all constructed candidate numbers. ### Follow-up Questions - What changes in the acceptance condition if the result is allowed to equal `n`? - How should an implementation account for the cost of constructing and comparing candidate decimal representations? ```hint Generate candidates from their counts Choose which nonzero digits appear. Palindrome symmetry restricts which of their required counts can be odd. Arrange the first half of a valid digit multiset and mirror it, placing any unpaired digit at the center. Prove a sufficient length bound before limiting candidate generation. ```