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 <= 105`
*   `num` is a **palindrome**.


from itertools import permutations


def nextPalindrome(num: str) -> str:
    n = len(num)
    first_half = num[:(n + 1) // 2]
    candidates = sorted(set(int("".join(p)) for p in permutations(first_half)))

    for c in candidates:
        c_str = str(c)
        second_half = c_str[::-1]
        if n % 2 == 1:
            second_half = second_half[1:]
        candidate_str = c_str + second_half

        if candidate_str > num:
            return candidate_str

    return ""
