How hard is LeetCode 1842. Next Palindrome Using Same Digits?

LeetCode 1842. Next Palindrome Using Same Digits is rated Hard on LeetCode.

What is the time complexity of LeetCode 1842. Next Palindrome Using Same Digits?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 1842. Next Palindrome Using Same Digits?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 1842. Next Palindrome Using Same Digits cover?

LeetCode 1842. Next Palindrome Using Same Digits is tagged Two Pointers and String on LeetCode.

Is LeetCode 1842. Next Palindrome Using Same Digits a premium problem?

Yes. LeetCode 1842. Next Palindrome Using Same Digits is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Next Palindrome Using Same Digits — LeetCode 1842 Python Solution

HardLeetCode PremiumTwo PointersString

Problem: #1842
Pattern: Two Pointers
Reading time: 4 min
Source: leetcode.com

The problem

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.

Example

Input: num = "1221"
Output: "2112"
Explanation: The next palindrome larger than "1221" is "2112".

Python solution

Python

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)

Complexity

Measure	Complexity
Time	O(n)
Space	O(n) auxiliary

Pattern: Two Pointers

Use the order already in the input to discard half the search space at every step. LeetCode 1842. Next Palindrome Using Same Digits is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Two Pointers.

The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1842. Next Palindrome Using Same Digits?: LeetCode 1842. Next Palindrome Using Same Digits is rated Hard on LeetCode.
What is the time complexity of LeetCode 1842. Next Palindrome Using Same Digits?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 1842. Next Palindrome Using Same Digits?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 1842. Next Palindrome Using Same Digits cover?: LeetCode 1842. Next Palindrome Using Same Digits is tagged Two Pointers and String on LeetCode.
Is LeetCode 1842. Next Palindrome Using Same Digits a premium problem?: Yes. LeetCode 1842. Next Palindrome Using Same Digits is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.