Formatted question description: https://leetcode.ca/all/1842.html

1842. Next Palindrome Using Same Digits

Level

Hard

Description

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 <= 10^5
num is a palindrome.

Solution

If num has an even length, then all characters occur even numbers of times. If num has an odd length, then only the middle character occurs an odd number of times, and the middle character must remain at the middle to make the string a palindrome. Therefore, only consider the first half of num.

Get the next permutation of the first half of num, and generate the second half of the next permutation of the first half to obtain the complete string of next palindrome.

class Solution {
    public String nextPalindrome(String num) {
        char[] arr = num.toCharArray();
        int length = arr.length;
        boolean flag = nextPermutation(arr, length / 2);
        if (!flag)
            return "";
        StringBuffer sb = new StringBuffer(new String(arr, 0, (length + 1) / 2));
        for (int i = length / 2 - 1; i >= 0; i--)
            sb.append(sb.charAt(i));
        return sb.toString();
    }

    public boolean nextPermutation(char[] arr, int endIndex) {
        int changeIndex = -1;
        for (int i = endIndex - 2; i >= 0; i--) {
            if (arr[i] < arr[i + 1]) {
                changeIndex = i;
                break;
            }
        }
        if (changeIndex < 0)
            return false;
        int nextIndex = -1;
        for (int i = endIndex - 1; i > changeIndex; i--) {
            if (arr[i] > arr[changeIndex]) {
                nextIndex = i;
                break;
            }
        }
        char temp = arr[changeIndex];
        arr[changeIndex] = arr[nextIndex];
        arr[nextIndex] = temp;
        reverse(arr, changeIndex + 1, endIndex - 1);
        return true;
    }

    public void reverse(char[] arr, int start, int end) {
        int low = start, high = end;
        while (low < high) {
            char temp = arr[low];
            arr[low] = arr[high];
            arr[high] = temp;
            low++;
            high--;
        }
    }
}

class Solution {
 public:
  string nextPalindrome(string num) {
    const int n = num.length();
    vector<int> A(n / 2);

    for (int i = 0; i < A.size(); ++i)
      A[i] = num[i] - '0';

    if (!nextPermutation(A))
      return "";

    string s;

    for (const int a : A)
      s += '0' + a;

    if (n & 1)
      return s + num[n / 2] + string(rbegin(s), rend(s));
    return s + string(rbegin(s), rend(s));
  }

 private:
  // Returns true if nums has next permutation
  bool nextPermutation(vector<int>& nums) {
    const int n = nums.size();

    // From back to front, find the first num < nums[i + 1]
    int i;
    for (i = n - 2; i >= 0; --i)
      if (nums[i] < nums[i + 1])
        break;

    if (i < 0)
      return false;

    // From back to front, find the first num > nums[i], swap it with nums[i]
    for (int j = n - 1; j > i; --j)
      if (nums[j] > nums[i]) {
        swap(nums[i], nums[j]);
        break;
      }

    // Reverse nums[i + 1..n - 1]
    reverse(nums, i + 1, n - 1);
    return true;
  }

  void reverse(vector<int>& nums, int l, int r) {
    while (l < r)
      swap(nums[l++], nums[r--]);
  }
};

class Solution:
  def nextPalindrome(self, num: str) -> str:
    def nextPermutation(nums: List[int]) -> bool:
      n = len(nums)

      # From back to front, find the first num < nums[i + 1]
      i = n - 2
      while i >= 0:
        if nums[i] < nums[i + 1]:
          break
        i -= 1

      if i < 0:
        return False

      # From back to front, find the first num > nums[i], swap it with nums[i]
      for j in range(n - 1, i, -1):
        if nums[j] > nums[i]:
          nums[i], nums[j] = nums[j], nums[i]
          break

      def reverse(nums, l, r):
        while l < r:
          nums[l], nums[r] = nums[r], nums[l]
          l += 1
          r -= 1

      # Reverse nums[i + 1..n - 1]
      reverse(nums, i + 1, len(nums) - 1)
      return True

    n = len(num)
    A = [ord(num[i]) - ord('0') for i in range(len(num) // 2)]

    if not nextPermutation(A):
      return ''

    s = ''.join([chr(ord('0') + a) for a in A])
    if n & 1:
      return s + num[n // 2] + s[::-1]
    return s + s[::-1]

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
}

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;
}

1842 - Next Palindrome Using Same Digits

1842. Next Palindrome Using Same Digits

Level

Description

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

1842. Next Palindrome Using Same Digits

Level

Description

Solution

All Problems

All Solutions