Skip to content

1842. Next Palindrome Using Same Digits 👍

  • Time: $O(n)$
  • Space: $O(n)$
 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
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 % 2 == 1)
      return s + num[n / 2] + reversed(s);
    return s + reversed(s);
  }

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

    // From the back to the 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 the back to the front, find the first num > nums[i] and 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--]);
  }

  string reversed(const string& s) {
    return {s.rbegin(), s.rend()};
  }
};

 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
  public String nextPalindrome(String num) {
    final int n = num.length();
    int[] A = new int[n / 2];

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

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

    StringBuilder sb = new StringBuilder();

    for (final int a : A)
      sb.append(a);

    if (n % 2 == 1)
      return sb.toString() + num.charAt(n / 2) + sb.reverse().toString();
    return sb.toString() + sb.reverse().toString();
  }

  private boolean nextPermutation(int[] nums) {
    final int n = nums.length;

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

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

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

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

 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution:
  def nextPalindrome(self, num: str) -> str:
    def nextPermutation(nums: list[int]) -> bool:
      n = len(nums)

      # From the back to the 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 the back to the front, find the first num > nums[i] and 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 = [int(num[i]) for i in range(len(num) // 2)]

    if not nextPermutation(A):
      return ''

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