Problem statement

https://leetcode.com/problems/next-palindrome-using-same-digits/

Solution

The idea is to use 0031 Next Permutation problem. We can consider only half of palindrome and what is asked to find next permutation of given half. It can be done in linear time, then we need to reconstruct palindrome.

Complexity

It is O(n) for time and space

Code

class Solution:
    def nextPalindrome(self, num):
        n = len(num)
        half = [i for i in num[:n//2]]
        m = len(half)

        i = m - 1
        while i-1 >= 0 and half[i] <= half[i-1]:
            i -= 1
            
        if i == 0: return ""

        j = i
        while j+1 < m and half[j+1] > half[i-1]:
            j += 1

        half[i-1], half[j] = half[j], half[i-1]
        half[i:] = half[i:][::-1]
        
        return "".join(half + [num[n//2]*(n%2 == 1)] + half[::-1])