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 <= 18n consists of only digits.n does not have leading zeros.n is representing an integer in the range [1, 1018 - 1].This approach involves mirroring the first half of the number to form the second half which can create a potential palindrome. After forming the basic mirrored palindrome, consider the numbers formed by adjusting the half upwards and downwards. This will cover all possible close numbers. Finally, choose the closest and smallest palindrome by comparing all options.
The C language solution creates a helper function to generate a mirrored palindrome given a string. It then creates potential palindrome candidates by mirroring the number, decrementing, and incrementing the middle digit(s). The closest candidate by absolute difference is selected as the solution.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) where n is the length of the string, as it involves mirroring which is a linear operation.
Space Complexity: O(n) for storing temporary palindrome strings.
palindromes were tricky until I learned this • NeetCode • 158,866 views views
Watch 9 more video solutions →Practice Find the Closest Palindrome with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor