Given a positive integer n, you are asked to find the next smallest palindrome that is strictly greater than n and uses exactly the same set of digits as n. The palindrome must be composed by rearranging all the digits of n (you cannot add or remove digits), and you must not reuse any digit more times than it appears in n. If such a palindrome does not exist, return -1.
n.n must be used exactly once in the palindrome.-1 if no such palindrome can be constructed.
At first glance, one might consider generating all permutations of the digits, checking if each one forms a palindrome, and then selecting the smallest palindrome greater than n. However, this brute-force approach is highly inefficient, especially for numbers with many digits, due to the exponential number of permutations.
Instead, we can optimize by leveraging properties of palindromes and permutations. Since a palindrome reads the same forwards and backwards, we only need to construct half (or just over half) of the palindrome and mirror it. Also, since we need the next palindrome, we can focus on finding the next lexicographically greater half, then mirror it to form a candidate. This is similar to the "next permutation" problem but with the added restriction of palindromic structure.
Let's break down the optimized solution step by step:
n. This helps us determine if a palindrome is possible (a palindrome can be formed if at most one digit has an odd count).
-1 in this case.
-1.
n. If not, continue to the next permutation.
-1.
This approach is efficient because it reduces the search space by only considering palindromic permutations and uses the next permutation algorithm to jump directly to the next candidate.
Let's walk through the process with an example: n = 1221.
2112.
If the next permutation does not produce a palindrome greater than n, we continue to the next permutation until all possibilities are exhausted.
n’s digits is O(k!), where k is the number of digits, which is infeasible for large k.
The key insight is that you only need to permute half of the palindrome and mirror it, which drastically reduces the number of candidates. By combining digit counting, palindrome properties, and the next permutation algorithm, we efficiently find the next palindrome using the same digits as the input, or report impossibility. This approach is both elegant and practical for real-world input sizes.
from collections import Counter
def next_permutation(arr):
# Find non-increasing suffix
i = len(arr) - 2
while i >= 0 and arr[i] >= arr[i + 1]:
i -= 1
if i == -1:
return False
# Find successor to pivot
j = len(arr) - 1
while arr[j] <= arr[i]:
j -= 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1:] = reversed(arr[i+1:])
return True
def next_palindrome(n):
s = str(n)
counter = Counter(s)
odd_digits = [d for d in counter if counter[d] % 2 == 1]
if len(odd_digits) > 1:
return -1
# Build half
half = []
for d in sorted(counter.keys()):
half.extend([d] * (counter[d] // 2))
half = list(half)
orig_half = half[:]
center = odd_digits[0] if odd_digits else ''
# Try next permutations
while next_permutation(half):
pal = ''.join(half) + center + ''.join(reversed(half))
if int(pal) > n:
return int(pal)
return -1
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
string nextPalindrome(string n) {
unordered_map<char, int> count;
for (char c : n) count[c]++;
vector<char> oddDigits;
for (auto &p : count)
if (p.second % 2 == 1) oddDigits.push_back(p.first);
if (oddDigits.size() > 1) return "-1";
vector<char> half;
for (char d = '0'; d <= '9'; ++d)
if (count.count(d))
half.insert(half.end(), count[d] / 2, d);
sort(half.begin(), half.end());
string center = oddDigits.empty() ? "" : string(1, oddDigits[0]);
string orig_half = string(half.begin(), half.end());
do {
string pal(half.begin(), half.end());
pal += center;
pal += string(half.rbegin(), half.rend());
if (pal > n) return pal;
} while (next_permutation(half.begin(), half.end()));
return "-1";
}
import java.util.*;
public class Solution {
public String nextPalindrome(String n) {
int[] count = new int[10];
for (char c : n.toCharArray())
count[c - '0']++;
int odd = 0, oddDigit = -1;
for (int d = 0; d < 10; d++)
if (count[d] % 2 == 1) {
odd++;
oddDigit = d;
}
if (odd > 1) return "-1";
List<Character> half = new ArrayList<>();
for (int d = 0; d < 10; d++)
for (int i = 0; i < count[d] / 2; i++)
half.add((char)('0' + d));
Collections.sort(half);
String center = (odd == 1) ? String.valueOf((char)('0' + oddDigit)) : "";
boolean found = false;
while (true) {
StringBuilder sb = new StringBuilder();
for (char c : half) sb.append(c);
String pal = sb.toString() + center + sb.reverse().toString();
if (pal.compareTo(n) > 0) return pal;
// next permutation
int i = half.size() - 2;
while (i >= 0 && half.get(i) >= half.get(i+1)) i--;
if (i < 0) break;
int j = half.size() - 1;
while (half.get(j) <= half.get(i)) j--;
Collections.swap(half, i, j);
Collections.reverse(half.subList(i+1, half.size()));
}
return "-1";
}
}
function nextPermutation(arr) {
let i = arr.length - 2;
while (i >= 0 && arr[i] >= arr[i+1]) i--;
if (i < 0) return false;
let j = arr.length - 1;
while (arr[j] <= arr[i]) j--;
[arr[i], arr[j]] = [arr[j], arr[i]];
let left = i + 1, right = arr.length - 1;
while (left < right) {
[arr[left], arr[right]] = [arr[right], arr[left]];
left++; right--;
}
return true;
}
function nextPalindrome(n) {
let s = n.toString();
let count = {};
for (let c of s) count[c] = (count[c] || 0) + 1;
let oddDigits = [];
for (let d in count)
if (count[d] % 2 === 1) oddDigits.push(d);
if (oddDigits.length > 1) return -1;
let half = [];
Object.keys(count).sort().forEach(d => {
for (let i = 0; i < Math.floor(count[d]/2); i++)
half.push(d);
});
let center = oddDigits.length ? oddDigits[0] : '';
while (nextPermutation(half)) {
let pal = half.join('') + center + half.slice().reverse().join('');
if (parseInt(pal) > parseInt(n)) return parseInt(pal);
}
return -1;
}