Next Palindrome Using Same Digits solution and explanation
4 more videos on this problem
1842. Next Palindrome Using Same Digits (Leetcode Hard)Programming Live with Larry · 25:47 · 627 views
1842. Next Palindrome Using Same DigitsJust Coding, with Jie · 14:21 · 330 views
LeetCode Hard: 1842 Next Palindrome Using Same Digitsrobzingcod · 24:41 · 98 views
Leetcode 1842 (hard) - Next Palindrome Using Same DigitsTechStack in Motion · 6:04 · 13 views
LeetCode 1842: Next Palindrome Using Same DigitsAlitaCode · 30:01 · 9 views
The problem
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.
Example 1:
Input: num = "1221" Output: "2112" Explanation: The next palindrome larger than "1221" is "2112".
Example 2:
Input: num = "32123" Output: "" Explanation: No palindromes larger than "32123" can be made by rearranging the digits.
Example 3:
Input: num = "45544554" Output: "54455445" Explanation: The next palindrome larger than "45544554" is "54455445".
Constraints:
1 <= num.length <= 105numis a palindrome.
Approach overview
Problem Overview: Given a numeric string that is already a palindrome, return the next larger palindrome that can be formed using exactly the same digits. If no larger palindrome exists, return an empty string. The result must preserve the palindrome structure while using the same multiset of digits.
Approach 1: Generate Permutations and Check Palindromes (Brute Force) (Time: O(n! * n), Space: O(n))
A naive strategy generates permutations of the digits and filters the ones that form valid palindromes. For each permutation, verify the palindrome condition by comparing characters from both ends using two pointers. Track the smallest palindrome strictly larger than the original value. This approach is impractical for large inputs because factorial growth quickly becomes unmanageable. It mainly helps illustrate the constraints of the problem: the palindrome structure means only half the digits actually determine the entire number.
Approach 2: Next Permutation of the First Half (Optimal) (Time: O(n), Space: O(n))
The key observation: a palindrome is fully determined by its first half. The second half is just the mirror of the first. Instead of permuting all digits, operate only on the left half of the string. Extract the first n/2 digits and compute the next lexicographically greater permutation using the standard next-permutation algorithm. This involves scanning from right to left to find the first decreasing element, swapping it with the next larger digit on its right, and reversing the suffix.
Once the next permutation of the left half is formed, rebuild the palindrome. If the length is even, mirror the entire half. If the length is odd, keep the middle digit unchanged and mirror only the left portion around it. Because next permutation guarantees the smallest lexicographically larger arrangement, the constructed palindrome is the next valid one using the same digits.
This method uses simple string manipulation and the classic permutation pattern while maintaining the palindrome invariant. The algorithm scans the string a few times, so the complexity stays linear.
Recommended for interviews: Interviewers expect the next-permutation insight. Recognizing that only the first half controls the palindrome drastically reduces the search space. Mentioning the brute-force idea shows understanding of the constraints, but implementing the half-permutation approach demonstrates strong algorithmic reasoning and familiarity with permutation patterns.
Solution
According to the problem description, we only need to find the next permutation of the first half of the string, then traverse the first half and symmetrically assign values to the second half.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the string.
class Solution:
def nextPalindrome(self, num: str) -> str:
def next_permutation(nums: List[str]) -> bool:
n = len(nums) // 2
i = n - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i < 0:
return False
j = n - 1
while j >= 0 and nums[j] <= nums[i]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
nums[i + 1 : n] = nums[i + 1 : n][::-1]
return True
nums = list(num)
if not next_permutation(nums):
return ""
n = len(nums)
for i in range(n // 2):
nums[n - i - 1] = nums[i]
return "".join(nums)class Solution {
public String nextPalindrome(String num) {
char[] nums = num.toCharArray();
if (!nextPermutation(nums)) {
return "";
}
int n = nums.length;
for (int i = 0; i < n / 2; ++i) {
nums[n - 1 - i] = nums[i];
}
return String.valueOf(nums);
}
private boolean nextPermutation(char[] nums) {
int n = nums.length / 2;
int i = n - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
--i;
}
if (i < 0) {
return false;
}
int j = n - 1;
while (j >= 0 && nums[i] >= nums[j]) {
--j;
}
swap(nums, i++, j);
for (j = n - 1; i < j; ++i, --j) {
swap(nums, i, j);
}
return true;
}
private void swap(char[] nums, int i, int j) {
char t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}class Solution {
public:
string nextPalindrome(string num) {
int n = num.size();
string nums = num.substr(0, n / 2);
if (!next_permutation(begin(nums), end(nums))) {
return "";
}
for (int i = 0; i < n / 2; ++i) {
num[i] = nums[i];
num[n - i - 1] = nums[i];
}
return num;
}
};function nextPalindrome(num: string): string {
const nums = num.split('');
const n = nums.length;
if (!nextPermutation(nums)) {
return '';
}
for (let i = 0; i < n >> 1; ++i) {
nums[n - 1 - i] = nums[i];
}
return nums.join('');
}
function nextPermutation(nums: string[]): boolean {
const n = nums.length >> 1;
let i = n - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i < 0) {
return false;
}
let j = n - 1;
while (j >= 0 && nums[i] >= nums[j]) {
j--;
}
[nums[i], nums[j]] = [nums[j], nums[i]];
for (i = i + 1, j = n - 1; i < j; ++i, --j) {
[nums[i], nums[j]] = [nums[j], nums[i]];
}
return true;
}func nextPalindrome(num string) string {
nums := []byte(num)
n := len(nums)
if !nextPermutation(nums) {
return ""
}
for i := 0; i < n/2; i++ {
nums[n-1-i] = nums[i]
}
return string(nums)
}
func nextPermutation(nums []byte) bool {
n := len(nums) / 2
i := n - 2
for i >= 0 && nums[i] >= nums[i+1] {
i--
}
if i < 0 {
return false
}
j := n - 1
for j >= 0 && nums[j] <= nums[i] {
j--
}
nums[i], nums[j] = nums[j], nums[i]
for i, j = i+1, n-1; i < j; i, j = i+1, j-1 {
nums[i], nums[j] = nums[j], nums[i]
}
return true
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Generate All Permutations and Check Palindromes | O(n! * n) | O(n) | Conceptual baseline or very small inputs |
| Next Permutation of First Half + Mirror | O(n) | O(n) | Optimal solution for interviews and production code |
Frequently asked questions
Is Next Palindrome Using Same Digits easy or hard?
The problem is rated Hard because the key insight is non-obvious. Many candidates initially attempt full permutations, but the correct solution reduces the search space by applying next permutation only to the first half of the palindrome.
Next Palindrome Using Same Digits Python/Java solution
Implement the next permutation algorithm on the first half of the string. Python typically converts the string to a list for swaps and reversal, while Java uses a char array. After computing the next half, mirror it to build the full palindrome.
How to solve Next Palindrome Using Same Digits in O(n)?
Extract the first half of the palindrome and apply the standard next permutation algorithm. After generating the next lexicographically larger arrangement of that half, rebuild the palindrome by mirroring it. If the string length is odd, keep the middle character unchanged and mirror the rest.
What is the best approach for Next Palindrome Using Same Digits?
The optimal approach computes the next permutation of the first half of the palindrome and mirrors it to rebuild the full number. Because a palindrome is determined entirely by its left half, modifying that portion generates the next valid candidate. This method runs in O(n) time and O(n) space.
Is Next Palindrome Using Same Digits asked at Google/Amazon/Meta?
Palindrome permutation and next-permutation style problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variations test understanding of lexicographic permutations, string manipulation, and two-pointer techniques.
What data structure is used in Next Palindrome Using Same Digits?
The solution mainly uses string or character array manipulation. The next-permutation process operates directly on an array of digits with swaps and reversals, while two-pointer comparisons are used conceptually when reasoning about palindrome structure.
What is the time complexity of Next Palindrome Using Same Digits?
The optimal algorithm runs in O(n) time because it scans the first half of the string to perform the next-permutation steps and then constructs the mirrored palindrome. Space complexity is O(n) due to string manipulation and rebuilding the result.