• Time:Time:
• Space:Space:

C++

``````class Solution {
public:
string nearestPalindromic(string n) {
const auto& [prevPalindrome, nextPalindrome] = getPalindromes(n);
return abs(prevPalindrome - stol(n)) <= abs(nextPalindrome - stol(n))
? to_string(prevPalindrome)
: to_string(nextPalindrome);
}

private:
pair<long, long> getPalindromes(const string& s) {
const long num = stol(s);
const int n = s.length();
pair<long, long> palindromes;
const string& half = s.substr(0, (n + 1) / 2);
const string& reversedHalf = reversed(half.substr(0, n / 2));
const long candidate = stol(half + reversedHalf);

if (candidate < num)
palindromes.first = candidate;
else {
const string& prevHalf = to_string(stol(half) - 1);
const string& reversedPrevHalf = reversed(prevHalf.substr(0, n / 2));
if (n % 2 == 0 && stol(prevHalf) == 0)
palindromes.first = 9;
else if (n % 2 == 0 && (stol(prevHalf) + 1) % 10 == 0)
palindromes.first = stol(prevHalf + '9' + reversedPrevHalf);
else
palindromes.first = stol(prevHalf + reversedPrevHalf);
}

if (candidate > num)
palindromes.second = candidate;
else {
const string& nextHalf = to_string(stol(half) + 1);
const string& reversedNextHalf = reversed(nextHalf.substr(0, n / 2));
palindromes.second = stol(nextHalf + reversedNextHalf);
}

return palindromes;
}

string reversed(const string& s) {
return {rbegin(s), rend(s)};
}
};
``````

JAVA

``````class Solution {
public String nearestPalindromic(String n) {
final long[] palindromes = getPalindromes(n);
return Math.abs(palindromes[0] - Long.parseLong(n)) <=
Math.abs(palindromes[1] - Long.parseLong(n))
? String.valueOf(palindromes[0])
: String.valueOf(palindromes[1]);
}

private long[] getPalindromes(final String s) {
final long num = Long.parseLong(s);
final int n = s.length();
long[] palindromes = new long[2];
final String half = s.substring(0, (n + 1) / 2);
final String reversedHalf = new StringBuilder(half.substring(0, n / 2)).reverse().toString();
final long candidate = Long.parseLong(half + reversedHalf);

if (candidate < num)
palindromes[0] = candidate;
else {
final String prevHalf = String.valueOf(Long.parseLong(half) - 1);
final String reversedPrevHalf =
new StringBuilder(prevHalf.substring(0, Math.min(prevHalf.length(), n / 2)))
.reverse()
.toString();
if (n % 2 == 0 && Long.parseLong(prevHalf) == 0)
palindromes[0] = 9;
else if (n % 2 == 0 && (Long.parseLong(prevHalf) + 1) % 10 == 0)
palindromes[0] = Long.parseLong(prevHalf + '9' + reversedPrevHalf);
else
palindromes[0] = Long.parseLong(prevHalf + reversedPrevHalf);
}

if (candidate > num)
palindromes[1] = candidate;
else {
final String nextHalf = String.valueOf(Long.parseLong(half) + 1);
final String reversedNextHalf =
new StringBuilder(nextHalf.substring(0, n / 2)).reverse().toString();
palindromes[1] = Long.parseLong(nextHalf + reversedNextHalf);
}

return palindromes;
}
}
``````

Python

``````class Solution:
def nearestPalindromic(self, n: str) -> str:
def getPalindromes(s: str) -> tuple:
num = int(s)
k = len(s)
palindromes = []
half = s[0:(k + 1) // 2]
reversedHalf = half[:k // 2][::-1]
candidate = int(half + reversedHalf)

if candidate < num:
palindromes.append(candidate)
else:
prevHalf = str(int(half) - 1)
reversedPrevHalf = prevHalf[:k // 2][::-1]
if k % 2 == 0 and int(prevHalf) == 0:
palindromes.append(9)
elif k % 2 == 0 and (int(prevHalf) + 1) % 10 == 0:
palindromes.append(int(prevHalf + '9' + reversedPrevHalf))
else:
palindromes.append(int(prevHalf + reversedPrevHalf))

if candidate > num:
palindromes.append(candidate)
else:
nextHalf = str(int(half) + 1)
reversedNextHalf = nextHalf[:k // 2][::-1]
palindromes.append(int(nextHalf + reversedNextHalf))

return palindromes

prevPalindrome, nextPalindrome = getPalindromes(n)
return str(prevPalindrome) if abs(prevPalindrome - int(n)) <= abs(nextPalindrome - int(n)) else str(nextPalindrome)
``````