Question

1842. 下个由相同数字构成的回文串

English Version

题目描述

给你一个很长的数字回文串 num ，返回 大于 num、由相同数字重新组合而成的最小 回文串。

如果不存在这样的回文串，则返回空串 ""。

回文串 是正读和反读都一样的字符串。

 

示例 1：

输入：num = "1221"
输出："2112"
解释：下个比 "1221" 大的回文串是 "2112"。

示例 2：

输入：num = "32123"
输出：""
解释：不存在通过重组 "32123" 的数字可得、比 "32123" 还大的回文串。

示例 3：

输入：num = "45544554"
输出："54455445"
解释：下个比 "45544554" 还要大的回文串是 "54455445"。

 

提示：

• 1 <= num.length <= 105
• num 是回文串。

解法

方法一：求前一半的下一个排列

根据题目描述，我们只需要求出前一半的下一个排列，然后遍历前一半，对称赋值后半部分即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为字符串长度。

class Solution:
  def nextPalindrome(self, num: str) -> str:
    def next_permutation(nums: List[str]) -> bool:
      n = len(nums) // 2
      i = n - 2
      while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
      if i < 0:
        return False
      j = n - 1
      while j >= 0 and nums[j] <= nums[i]:
        j -= 1
      nums[i], nums[j] = nums[j], nums[i]
      nums[i + 1 : n] = nums[i + 1 : n][::-1]
      return True

    nums = list(num)
    if not next_permutation(nums):
      return ""
    n = len(nums)
    for i in range(n // 2):
      nums[n - i - 1] = nums[i]
    return "".join(nums)

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

  private boolean nextPermutation(char[] nums) {
    int n = nums.length / 2;
    int i = n - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
      --i;
    }
    if (i < 0) {
      return false;
    }
    int j = n - 1;
    while (j >= 0 && nums[i] >= nums[j]) {
      --j;
    }
    swap(nums, i++, j);
    for (j = n - 1; i < j; ++i, --j) {
      swap(nums, i, j);
    }
    return true;
  }

  private void swap(char[] nums, int i, int j) {
    char t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
  }
}

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

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