Leetcode 1842. Next Palindrome Using Same Digits

Problem Description

You are given a numeric string num, representing a very large palindrome. Your goal is to 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 <= 105
• num is a palindrome.

Approach

To solve this problem, we can use the following algorithm:

1. Create a vector A containing the first half of the characters in the input string num.
2. Apply the "next permutation" function on the vector A. This function will rearrange the digits in the vector to create the next greater permutation.
3. If there is no next greater permutation, return an empty string.
4. Reconstruct the palindrome from the modified vector A.
5. Return the reconstructed palindrome.

Walkthrough

Let's walk through an example with the input num = "1221".

1. Create the vector A containing the first half of the characters in num: [1, 2].
2. Apply the "next permutation" function on A, getting the new vector [2, 1].
3. Since there is a next greater permutation, we can proceed to step 4.
4. Reconstruct the palindrome from the modified A: The result is "2112".
5. Return the reconstructed palindrome: "2112".

Solution in Python

1from itertools import permutations
2
3class Solution:
4    def nextPalindrome(self, num: str) -> str:
5        n = len(num)
6        A = [int(x) for x in num[:n // 2]]
7        
8        next_permutation = None
9        for perm in sorted(permutations(A)):
10            if tuple(A) < perm:
11                next_permutation = perm
12                break
13        
14        if not next_permutation:
15            return ""
16        
17        s = "".join(str(x) for x in next_permutation)
18        if n % 2 == 1:
19            return s + num[n // 2] + s[::-1]
20        return s + s[::-1]

Solution in Java

1import java.util.Arrays;
2
3class Solution {
4    public String nextPalindrome(String num) {
5        int n = num.length();
6        int[] A = new int[n / 2];
7
8        for (int i = 0; i < A.length; ++i) {
9            A[i] = num.charAt(i) - '0';
10        }
11
12        int[] nextPermutation = nextPermutation(A);
13        if (nextPermutation == null) {
14            return "";
15        }
16
17        StringBuilder sb = new StringBuilder();
18        for (int a : nextPermutation) {
19            sb.append(a);
20        }
21
22        if (n % 2 == 1) {
23            return sb.toString() + num.charAt(n / 2) + sb.reverse().toString();
24        }
25        return sb.toString() + sb.reverse().toString();
26    }
27
28    private int[] nextPermutation(int[] nums) {
29        int n = nums.length;
30        int i = n - 2;
31        while (i >= 0 && nums[i] >= nums[i + 1]) {
32            --i;
33        }
34
35        if (i < 0) {
36            return null;
37        }
38
39        int j = n - 1;
40        while (j > i && nums[j] <= nums[i]) {
41            --j;
42        }
43
44        // swap nums[i] and nums[j]
45        int temp = nums[i];
46        nums[i] = nums[j];
47        nums[j] = temp;
48
49        // reverse nums[i + 1 .. n - 1]
50        int l = i + 1, r = n - 1;
51        while (l < r) {
52            temp = nums[l];
53            nums[l] = nums[r];
54            nums[r] = temp;
55            ++l;
56            --r;
57        }
58        return nums;
59    }
60}

Solution in JavaScript

1var nextPermutation = function(nums) {
2    let i = nums.length - 2;
3    while (i >= 0 && nums[i] >= nums[i + 1]) {
4        i--;
5    }
6    if (i < 0) return null;
7    
8    let j = nums.length - 1;
9    while (j > i && nums[j] <= nums[i]) {
10        j--;
11    }
12    [nums[i], nums[j]] = [nums[j], nums[i]];
13    nums.slice(i + 1).reverse().forEach((x, idx) => nums[idx + i + 1] = x);
14    return nums;
15};
16
17var nextPalindrome = function(num) {
18    let n = num.length, A = [];
19    for (let i = 0; i < n / 2; ++i) {
20        A[i] = parseInt(num[i]);
21    }
22    let nextPermutation = nextPermutation(A);
23    if (nextPermutation === null) return "";
24    let s = nextPermutation.join("");
25    if (n % 2) return s + num[n / 2] + s.split("").reverse().join("");
26    return s + s.split("").reverse().join("");
27};

Solution in C++

1#include <algorithm>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7    std::string nextPalindrome(std::string num) {
8        int n = num.size();
9        std::vector<int> A(n / 2);
10
11        for (int i = 0; i < A.size(); ++i)
12            A[i] = num[i] - '0';
13
14        if (!std::next_permutation(A.begin(), A.end()))
15            return "";
16
17        std::string s;
18
19        for (const int a : A)
20            s += '0' + a;
21
22        if (n % 2)
23            return s + num[n / 2] + std::string(s.rbegin(), s.rend());
24        return s + std::string(s.rbegin(), s.rend());
25    }
26};

Solution in C#

1using System;
2
3public class Solution {
4    public string NextPalindrome(string num) {
5        int n = num.Length;
6        int[] A = new int[n / 2];
7
8        for (int i = 0; i < A.Length; ++i) {
9            A[i] = num[i] - '0';
10        }
11
12        if (!NextPermutation(A)) {
13            return "";
14        }
15
16        string s = "";
17
18        foreach (int a in A) {
19            s += (char)('0' + a);
20        }
21
22        if (n % 2 == 1) {
23            return s + num[n / 2] + new string(s.ToCharArray().Reverse().ToArray());
24        }
25        return s + new string(s.ToCharArray().Reverse().ToArray());
26    }
27
28    private bool NextPermutation(int[] nums) {
29        int n = nums.Length;
30        int i = n - 2;
31
32        while (i >= 0 && nums[i] >= nums[i + 1]) {
33            --i;
34        }
35
36        if (i < 0) {
37            return false;
38        }
39
40        int j = n - 1;
41
42        while (j > i && nums[j] <= nums[i]) {
43            --j;
44        }
45
46        Swap(ref nums[i], ref nums[j]);
47        Array.Reverse(nums, i + 1, n - i - 1);
48        return true;
49    }
50
51    private static void Swap(ref int a, ref int b) {
52        int temp = a;
53        a = b;
54        b = temp;
55    }
56}
57```## Conclusion
58
59In conclusion, we present the solutions to find the next greater palindrome of a given numeric string `num` in Python, JavaScript, Java, C++, and C#. We first created a vector or array containing the first half of the characters in the input string, then applied the "next permutation" function on it to find the next greater permutation. If found, we reconstructed the palindrome from the modified vector or array and returned it. If there was no next greater permutation, we returned an empty string.