Next Palindrome Using Same Digits

class Solution {
public:
    string nextPalindrome(string num) {
        int n = num.size();
        int half = n / 2;
        if (!next_permutation(num.begin(), num.begin() + half)) return "";
        for (int i = 0; i < half; ++i) num[n - 1 - i] = num[i];
        return num;
    }
};

func nextPalindrome(num string) string {
    n := len(num)
    half := n / 2
    b := []byte(num)
    if !nextPermutation(b[:half]) {
        return ""
    }
    for i := 0; i < half; i++ {
        b[n-1-i] = b[i]
    }
    return string(b)
}

func nextPermutation(a []byte) bool {
    n := len(a)
    i := n - 2
    for i >= 0 && a[i] >= a[i+1] {
        i--
    }
    if i < 0 {
        return false
    }
    j := n - 1
    for a[j] <= a[i] {
        j--
    }
    a[i], a[j] = a[j], a[i]
    for l, r := i+1, n-1; l < r; l, r = l+1, r-1 {
        a[l], a[r] = a[r], a[l]
    }
    return true
}

class Solution:
    def nextPalindrome(self, num: str) -> str:
        n = len(num)
        half = n // 2
        b = list(num)
        if not self._next_permutation(b, 0, half):
            return ""
        for i in range(half):
            b[n - 1 - i] = b[i]
        return "".join(b)

    def _next_permutation(self, a: list, lo: int, hi: int) -> bool:
        # next_permutation on a[lo:hi]
        n = hi - lo
        i = n - 2
        while i >= 0 and a[lo + i] >= a[lo + i + 1]:
            i -= 1
        if i < 0:
            return False
        j = n - 1
        while a[lo + j] <= a[lo + i]:
            j -= 1
        a[lo + i], a[lo + j] = a[lo + j], a[lo + i]
        l, r = lo + i + 1, lo + n - 1
        while l < r:
            a[l], a[r] = a[r], a[l]
            l += 1
            r -= 1
        return True

function nextPalindrome(num) {
    const n = num.length;
    const half = Math.floor(n / 2);
    const b = num.split('');
    if (!nextPerm(b, 0, half)) return "";
    for (let i = 0; i < half; i++) {
        b[n - 1 - i] = b[i];
    }
    return b.join('');
}

function nextPerm(a, lo, hi) {
    const n = hi - lo;
    let i = n - 2;
    while (i >= 0 && a[lo + i] >= a[lo + i + 1]) i--;
    if (i < 0) return false;
    let j = n - 1;
    while (a[lo + j] <= a[lo + i]) j--;
    [a[lo + i], a[lo + j]] = [a[lo + j], a[lo + i]];
    let l = lo + i + 1, r = lo + n - 1;
    while (l < r) {
        [a[l], a[r]] = [a[r], a[l]];
        l++; r--;
    }
    return true;
}

class Solution {
    public String nextPalindrome(String num) {
        int n = num.length();
        int half = n / 2;
        char[] b = num.toCharArray();
        if (!nextPerm(b, 0, half)) return "";
        for (int i = 0; i < half; i++) {
            b[n - 1 - i] = b[i];
        }
        return new String(b);
    }

    private boolean nextPerm(char[] a, int lo, int hi) {
        int n = hi - lo;
        int i = n - 2;
        while (i >= 0 && a[lo + i] >= a[lo + i + 1]) i--;
        if (i < 0) return false;
        int j = n - 1;
        while (a[lo + j] <= a[lo + i]) j--;
        char tmp = a[lo + i]; a[lo + i] = a[lo + j]; a[lo + j] = tmp;
        int l = lo + i + 1, r = lo + n - 1;
        while (l < r) {
            char t = a[l]; a[l] = a[r]; a[r] = t;
            l++; r--;
        }
        return true;
    }
}

function nextPalindrome(num: string): string {
    const n = num.length;
    const half = Math.floor(n / 2);
    const b: string[] = num.split('');
    if (!nextPerm(b, 0, half)) return "";
    for (let i = 0; i < half; i++) {
        b[n - 1 - i] = b[i];
    }
    return b.join('');
}

function nextPerm(a: string[], lo: number, hi: number): boolean {
    const n = hi - lo;
    let i = n - 2;
    while (i >= 0 && a[lo + i] >= a[lo + i + 1]) i--;
    if (i < 0) return false;
    let j = n - 1;
    while (a[lo + j] <= a[lo + i]) j--;
    [a[lo + i], a[lo + j]] = [a[lo + j], a[lo + i]];
    let l = lo + i + 1, r = lo + n - 1;
    while (l < r) {
        [a[l], a[r]] = [a[r], a[l]];
        l++; r--;
    }
    return true;
}