Next Palindrome Using Same Digits

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

#include <algorithm>
string nextPalindrome(string num) {
    int n = num.size();
    int half = n / 2;
    string left = num.substr(0, half);
    string mid = n % 2 ? string(1, num[half]) : "";
    if (!next_permutation(left.begin(), left.end())) return "";
    string right = left;
    reverse(right.begin(), right.end());
    string res = left + mid + right;
    return res > num ? res : "";
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

import "sort"
func nextPalindrome(num string) string {
    n := len(num)
    half := n / 2
    left := []byte(num[:half])
    mid := ""
    if n%2 == 1 { mid = string(num[half]) }
    if !nextPermutation(left) { return "" }
    right := make([]byte, half)
    copy(right, left)
    for i := 0; i < half/2; i++ { right[i], right[half-1-i] = right[half-1-i], right[i] }
    res := string(left) + mid + string(right)
    if res > num { return res } else { return "" }
}
func nextPermutation(nums []byte) bool {
    i := len(nums) - 2
    for i >= 0 && nums[i] >= nums[i+1] { i-- }
    if i < 0 { return false }
    j := len(nums) - 1
    for nums[j] <= nums[i] { j-- }
    nums[i], nums[j] = nums[j], nums[i]
    for l, r := i+1, len(nums)-1; l < r; l, r = l+1, r-1 {
        nums[l], nums[r] = nums[r], nums[l]
    }
    return true
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

public String nextPalindrome(String num) {
    int n = num.length(), half = n / 2;
    char[] left = num.substring(0, half).toCharArray();
    String mid = n % 2 == 1 ? String.valueOf(num.charAt(half)) : "";
    if (!nextPermutation(left)) return "";
    StringBuilder right = new StringBuilder(new String(left)).reverse();
    String res = new String(left) + mid + right.toString();
    return res.compareTo(num) > 0 ? res : "";
}
private boolean nextPermutation(char[] arr) {
    int i = arr.length - 2;
    while (i >= 0 && arr[i] >= arr[i+1]) i--;
    if (i < 0) return false;
    int j = arr.length - 1;
    while (arr[j] <= arr[i]) j--;
    char tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
    for (int l = i+1, r = arr.length-1; l < r; l++, r--) {
        tmp = arr[l]; arr[l] = arr[r]; arr[r] = tmp;
    }
    return true;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

fun nextPalindrome(num: String): String {
    val n = num.length
    val half = n / 2
    val left = num.substring(0, half).toCharArray()
    val mid = if (n % 2 == 1) num[half].toString() else ""
    if (!nextPermutation(left)) return ""
    val right = left.reversed().joinToString("")
    val res = left.joinToString("") + mid + right
    return if (res > num) res else ""
}
fun nextPermutation(arr: CharArray): Boolean {
    var i = arr.size - 2
    while (i >= 0 && arr[i] >= arr[i+1]) i--
    if (i < 0) return false
    var j = arr.size - 1
    while (arr[j] <= arr[i]) j--
    arr[i] = arr[j].also { arr[j] = arr[i] }
    arr.reverse(i+1, arr.size)
    return true
}
fun CharArray.reverse(from: Int, to: Int) {
    var l = from; var r = to-1
    while (l < r) {
        val tmp = this[l]; this[l] = this[r]; this[r] = tmp
        l++; r--
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def nextPalindrome(num: str) -> str:
    n = len(num)
    half = n // 2
    left = list(num[:half])
    mid = num[half] if n % 2 else ''
    if not next_permutation(left): return ''
    right = left[::-1]
    res = ''.join(left) + mid + ''.join(right)
    return res if res > num else ''

def next_permutation(arr):
    i = len(arr) - 2
    while i >= 0 and arr[i] >= arr[i+1]: i -= 1
    if i < 0: return False
    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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

fn next_palindrome(num: &str) -> String {
    let n = num.len();
    let half = n / 2;
    let mut left: Vec<char> = num[..half].chars().collect();
    let mid = if n % 2 == 1 { num.chars().nth(half).unwrap().to_string() } else { String::new() };
    if !next_permutation(&mut left) { return String::new(); }
    let right: String = left.iter().rev().collect();
    let res = left.iter().collect::<String>() + &mid + &right;
    if res > num { res } else { String::new() }
}
fn next_permutation(arr: &mut [char]) -> bool {
    if arr.len() < 2 { return false; }
    let mut i = arr.len() - 2;
    while i > 0 && arr[i] >= arr[i+1] { i -= 1; }
    if i == 0 && arr[i] >= arr[i+1] { return false; }
    let mut j = arr.len() - 1;
    while arr[j] <= arr[i] { j -= 1; }
    arr.swap(i, j);
    arr[i+1..].reverse();
    true
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

function nextPalindrome(num: string): string {
    const n = num.length;
    const half = Math.floor(n / 2);
    let left = num.slice(0, half).split("");
    const mid = n % 2 ? num[half] : "";
    if (!nextPermutation(left)) return "";
    const right = [...left].reverse();
    const res = left.join("") + mid + right.join("");
    return res > num ? res : "";
}
function nextPermutation(arr: string[]): boolean {
    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 l = i+1, r = arr.length-1;
    while (l < r) {
        [arr[l], arr[r]] = [arr[r], arr[l]];
        l++; r--;
    }
    return true;
}