Problem Description
Explanation
To find the closest palindrome to a given integer represented as a string, we can follow these steps:
- Convert the input string to a long integer.
- Find the nearest smaller and nearest larger palindrome numbers.
- Calculate the absolute differences between the input number and the two palindrome numbers.
- Return the palindrome number with the smallest absolute difference. If there is a tie, return the smaller palindrome number.
Time Complexity: O(n) where n is the length of the input string. Space Complexity: O(1)
Solutions
class Solution {
public String nearestPalindromic(String n) {
long num = Long.parseLong(n);
long smaller = findSmallerPalindrome(num);
long larger = findLargerPalindrome(num);
return String.valueOf(smaller - num <= num - larger ? smaller : larger);
}
private long findSmallerPalindrome(long num) {
String str = String.valueOf(num);
String half = str.substring(0, (str.length() + 1) / 2);
String smallerHalf = String.valueOf(Long.parseLong(half) - 1);
boolean evenLen = str.length() % 2 == 0;
String smallerPalindrome = evenLen ? smallerHalf + new StringBuilder(smallerHalf).reverse().toString() : smallerHalf + new StringBuilder(smallerHalf.substring(0, smallerHalf.length() - 1)).reverse().toString();
return Long.parseLong(smallerPalindrome);
}
private long findLargerPalindrome(long num) {
String str = String.valueOf(num);
String half = str.substring(0, (str.length() + 1) / 2);
String largerHalf = String.valueOf(Long.parseLong(half) + 1);
boolean evenLen = str.length() % 2 == 0;
String largerPalindrome = evenLen ? largerHalf + new StringBuilder(largerHalf).reverse().toString() : largerHalf + new StringBuilder(largerHalf.substring(0, largerHalf.length() - 1)).reverse().toString();
return Long.parseLong(largerPalindrome);
}
}Related LeetCode Problems
Loading editor...