unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 1842: Next Palindrome Using Same Digits

link

Since num is a palindrome, if there is a center, it cannot be rearranged because the center is the only digit having odd count. We can rearrange the digits in one of the two halves only because, the other half would be mirror-image. So, we rearrange left half.

If the digits were sorted in non-increasing order, we could not make it bigger by rearranging them. So, to be able to increase, there must be a pair of indices (i, j) where i < j and num[i] < num[j]. Note, we want the increase to be as small as possible. So, we are looking for the (i, j) that is as right (at less significant digits) as possible. Beginning from right we scan leftwards and the first i we find is the left target for swap. For the right target of the swap, there might be a better choice than j. If there is a k such that k > j and num[i] < num[k] then num[k] is a better choice for the right target of the swap.

Once, we have made the swap and found a bigger number, we then try making it as small as possible still keeping it bigger than the original left half.

Time: \mathcal{O}(n), space: \mathcal{O}(n).

class Solution:
    def reverse(self, num, left, right):
        while left < right:
            num[left], num[right] = num[right], num[left]
            left += 1
            right -= 1

    def next_bigger(self, num):
        i = len(num)-1
        while i > 0:
            if num[i-1] < num[i]:
                break
            i -= 1

        if i <= 0:
            return None
        
        left = i-1
        right = len(num)-1
        while right > left:
            if num[left] < num[right]:
                break
            right -= 1
        
        num[left], num[right] = num[right], num[left]
        self.reverse(num, left+1, len(num)-1)
        return num

    def nextPalindrome(self, num: str) -> str:
        mid = len(num) // 2
        left_half = list(num[0:mid])
        bigger_left_half = self.next_bigger(left_half)
        if not bigger_left_half:
            return ""
        
        if len(num) % 2 == 1:
            return "".join(bigger_left_half) + num[mid] + "".join(bigger_left_half[::-1])
        else:
            return "".join(bigger_left_half) + "".join(bigger_left_half[::-1])

tanvirdotzaman

Leave a comment