Find the Nearest Different Decimal Palindrome
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
The string n represents a positive integer. Return the nearest palindromic integer as a decimal string, excluding the input integer itself. Minimize absolute difference and choose the smaller palindrome if distances tie.
```cpp
class Solution {
public:
string nearestPalindromic(string n);
};
```
### Examples
**Example 1:**
```text
n = "128"
Output: "131"
Explanation: Distances to 121 and 131 are 7 and 3.
```
**Example 2:**
```text
n = "100"
Output: "99"
Explanation: 99 and 101 tie; choose 99.
```
### Constraints
- The decimal input has 1..18 digits, no leading zero, and represents a value from 1 through 999999999999999999.
### Clarifying Questions
Exclude n itself, preserve smaller-value ties, and include digit-length boundaries.
```hint Read the boundary condition
Which leading-half adjustments can supply the immediately neighboring palindromes?
```
### Contract considerations
Exclude n itself, preserve smaller-value ties, and include digit-length boundaries.
Overview: Find the Nearest Different Decimal Palindrome. The string n represents a positive integer.
