Given a string n representing an integer, return the closest integer (not including itself), which is a palindrome. If there is a tie, return the smaller one.
The closest is defined as the absolute difference minimized between two integers.
Example 1:
Input: n = "123" Output: "121"
Example 2:
Input: n = "1" Output: "0" Explanation: 0 and 2 are the closest palindromes but we return the smallest which is 0.
Constraints:
1 <= n.length <= 18nconsists of only digits.ndoes not have leading zeros.nis representing an integer in the range[1, 1018 - 1].
Approach 01:
-
C++
-
Python
class Solution {
public:
string nearestPalindromic(string number) {
const auto& [previousPalindrome, nextPalindrome] = getClosestPalindromes(number);
return abs(previousPalindrome - stol(number)) <= abs(nextPalindrome - stol(number))
? to_string(previousPalindrome)
: to_string(nextPalindrome);
}
private:
// Returns the two closest palindromes to the given number.
pair<long, long> getClosestPalindromes(const string& number) {
const long originalNumber = stol(number);
const int length = number.length();
pair<long, long> closestPalindromes;
const string halfNumber = number.substr(0, (length + 1) / 2);
const string reversedHalfNumber = reverseString(halfNumber.substr(0, length / 2));
const long candidatePalindrome = stol(halfNumber + reversedHalfNumber);
if (candidatePalindrome < originalNumber) {
closestPalindromes.first = candidatePalindrome;
} else {
const string previousHalf = to_string(stol(halfNumber) - 1);
const string reversedPreviousHalf = reverseString(previousHalf.substr(0, length / 2));
if (length % 2 == 0 && stol(previousHalf) == 0) {
closestPalindromes.first = 9;
} else if (length % 2 == 0 && previousHalf == "9") {
closestPalindromes.first = stol(previousHalf + '9' + reversedPreviousHalf);
} else {
closestPalindromes.first = stol(previousHalf + reversedPreviousHalf);
}
}
if (candidatePalindrome > originalNumber) {
closestPalindromes.second = candidatePalindrome;
} else {
const string& nextHalf = to_string(stol(halfNumber) + 1);
const string& reversedNextHalf = reverseString(nextHalf.substr(0, length / 2));
closestPalindromes.second = stol(nextHalf + reversedNextHalf);
}
return closestPalindromes;
}
string reverseString(const string& str) {
return {str.rbegin(), str.rend()};
}
};
class Solution:
def nearestPalindromic(self, number: str) -> str:
previousPalindrome, nextPalindrome = self.getClosestPalindromes(number)
return str(previousPalindrome) if abs(previousPalindrome - int(number)) <= abs(nextPalindrome - int(number)) else str(nextPalindrome)
def getClosestPalindromes(self, number: str) -> (int, int):
originalNumber = int(number)
length = len(number)
closestPalindromes = (0, 0)
halfNumber = number[:(length + 1) // 2]
reversedHalfNumber = self.reverseString(halfNumber[:length // 2])
candidatePalindrome = int(halfNumber + reversedHalfNumber)
if candidatePalindrome < originalNumber:
closestPalindromes = (candidatePalindrome, closestPalindromes[1])
else:
previousHalf = str(int(halfNumber) - 1)
reversedPreviousHalf = self.reverseString(previousHalf[:length // 2])
if length % 2 == 0 and int(previousHalf) == 0:
closestPalindromes = (9, closestPalindromes[1])
elif length % 2 == 0 and previousHalf == "9":
closestPalindromes = (int(previousHalf + '9' + reversedPreviousHalf), closestPalindromes[1])
else:
closestPalindromes = (int(previousHalf + reversedPreviousHalf), closestPalindromes[1])
if candidatePalindrome > originalNumber:
closestPalindromes = (closestPalindromes[0], candidatePalindrome)
else:
nextHalf = str(int(halfNumber) + 1)
reversedNextHalf = self.reverseString(nextHalf[:length // 2])
closestPalindromes = (closestPalindromes[0], int(nextHalf + reversedNextHalf))
return closestPalindromes
def reverseString(self, s: str) -> str:
return s[::-1]
Time Complexity
- String Manipulation and Conversion:
The operations for manipulating and converting strings (such as reversing the string, converting between strings and numbers, and calculating the length) take \( O(n) \) time, where \( n \) is the length of the input string
number. - Finding Closest Palindromes:
The function
getClosestPalindromescomputes the two nearest palindromes by processing the first half of the string, reversing it, and performing a few arithmetic operations. These steps also take \( O(n) \) time. - Overall Time Complexity:
The overall time complexity is \( O(n) \), since the dominant operations involve processing the string and its substrings.
Space Complexity
- Auxiliary Space:
The auxiliary space is primarily used for storing the reversed strings, half of the number, and the resulting palindromes. These require \( O(n) \) space.
- Overall Space Complexity:
The overall space complexity is \( O(n) \), due to the additional strings created and stored during the palindrome computation.