LeetCode 564: Find the Closest Palindrome Solution
Master LeetCode problem 564 (Find the Closest Palindrome), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
Problem Explanation
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)
Solution Code
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);
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 564 (Find the Closest Palindrome)?
This page provides optimized solutions for LeetCode problem 564 (Find the Closest Palindrome) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 564 (Find the Closest Palindrome)?
The time complexity for LeetCode 564 (Find the Closest Palindrome) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 564 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 564 in Java, C++, or Python.