Find the closest palindrome

Math String

31.8% acceptance

Jan 13, 2026

1321

1738

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.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn nearest_palindromic(n: String) -> String {
    let len = n.len();
    let num: i64 = n.parse().unwrap();
    let mut candidates: Vec<i64> = Vec::new();
    // Edge: 10^(len-1) - 1 (e.g. 999 for length 4 input)
    candidates.push(10i64.pow((len - 1) as u32) - 1);
    // Edge: 10^len + 1
    candidates.push(10i64.pow(len as u32) + 1);
    // Mirror first half
    let half = &n[..(len + 1) / 2];
    let prefix: i64 = half.parse().unwrap();
    for delta in [-1i64, 0, 1] {
      let p = prefix + delta;
      let p_str = p.to_string();
      let mirrored = if len % 2 == 0 {
        let rev: String = p_str.chars().rev().collect();
        format!("{}{}", p_str, rev)
      } else {
        let rev: String = p_str.chars().rev().skip(1).collect();
        format!("{}{}", p_str, rev)
      };
      if let Ok(v) = mirrored.parse::<i64>() {
        candidates.push(v);
      }
    }
    candidates.retain(|&c| c != num);
    candidates.sort_by_key(|&c| (c - num).abs());
    let best = candidates.iter().min_by(|&&a, &&b| {
      let da = (a - num).abs();
      let db = (b - num).abs();
      da.cmp(&db).then(a.cmp(&b))
    }).unwrap();
    best.to_string()
  }
}