# Find the Closest Palindrome

This page explains Java solution to problem `Find the Closest Palindrome` using `String` data structure.

## Problem Statement

Given an integer `n`, find the closest integer (not including itself), which is a palindrome.

The 'closest' is defined as absolute difference minimized between two integers.

Example 1:

Input: "123"
Output: "121"

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

import java.util.HashSet;

class FindClosestPalindrome {
public String nearestPalindromic(String n) {
int len = n.length();

int middleIndex = len % 2 == 0 ? len / 2 - 1: len / 2;
long prefix = Long.parseLong(n.substring(0, middleIndex + 1));

HashSet<Long> candidates = new HashSet<>();
candidates.add(helper(prefix, len % 2 == 1));
candidates.add(helper(prefix + 1,  len % 2 == 1));
candidates.add(helper(prefix - 1,  len % 2 == 1));
candidates.add((long)Math.pow(10, len - 1) - 1);

long diff = Long.MAX_VALUE;
long res = Long.MAX_VALUE;
long number = Long.parseLong(n);
for(long candidate: candidates) {
if(candidate == number) continue;
else {
if(Math.abs(number - candidate) < diff) {
diff = Math.abs(number - candidate);
res = candidate;
}
else if(Math.abs(number - candidate) == diff) {
res = Math.min(candidate, res);
}
}
}
return String.valueOf(res);
}

private long helper(long left, boolean isLengthOdd) {
long res = left;
if(isLengthOdd) left = left / 10;
while(left > 0) {
res *= 10;
res += left % 10;
left /= 10;
}
return res;
}
}
``````

## Time Complexity

O(L) Where
L is length of input number

O(1)