Next palindrome using same digits

Two Pointers String

54.2% acceptance

Mar 31, 2026

126

You are given a numeric string num, representing a very large palindrome. Return the smallest palindrome larger than num that can be created by rearranging its digits. If no such palindrome exists, return an empty string "". A palindrome is a number that reads the same backward as forward.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn next_palindrome(num: String) -> String {
    let n = num.len();
    let mut chars: Vec<u8> = num.into_bytes();
    let half_len = n / 2;
    if half_len == 0 {
      return String::new();
    }
    let mut half: Vec<u8> = chars[..half_len].to_vec();
    if !Self::next_permutation(&mut half) {
      return String::new();
    }
    for i in 0..half_len {
      chars[i] = half[i];
      chars[n - 1 - i] = half[i];
    }
    String::from_utf8(chars).unwrap()
  }

  fn next_permutation(arr: &mut [u8]) -> bool {
    let n = arr.len();
    if n <= 1 {
      return false;
    }
    let mut i = n - 1;
    while i > 0 && arr[i - 1] >= arr[i] {
      i -= 1;
    }
    if i == 0 {
      return false;
    }
    let mut j = n - 1;
    while arr[j] <= arr[i - 1] {
      j -= 1;
    }
    arr.swap(i - 1, j);
    arr[i..].reverse();
    true
  }
}