Next Palindrome problem - PALIN

general
, , ,
1

Please help me optimize this code. Also please suggest me tips for competitive coding in python 3.

def nextPal(n):

    n = str(int(n))
    if (n=='9'): return 11
    if(n=='99'): return 101
    l = len(n)

    
    if(l<2): return int(n)+1
    
    if(int(n)<99):
        if(int(n[0])>int(n[1])):
            return n[0]+n[0]
        nt = str(int(n[0])+1)
        return nt+nt
    
    h = l//2
    
    if(l%2==0):
        n1 = int(n[:h])
        n2 = int(n[h:])
        
        if(int(n[:h:-1])>n2):
            return n[:h]+n[:h:-1]
        nt = str(int(n[:h])+1)
        return nt + nt[::-1]
    
    n1 = n[:h]
    m =  n[h]
    n2 = n[h+1:]
    
    if(int(n1[::-1])>int(n2)):
        return n1 + m + n1[::-1]
    nt = str(  int(n1+m) + 1  )
    return nt + nt[:-1][::-1]

for _ in range(int(input().strip())):

    print (nextPal(input().strip()))
2

While Python will convert any size valid string to integer, that’s a very slow way to handle this problem since it involves huge numbers of digits. Better to handle the whole process largely in strings, one character at a time (possibly converting that one character to int if needed).

So: don’t convert the input, just use it as a string immediately. You can discard surrounding whitespace with .strip() Length of 1 will probably need to be handled much as you do here.

Then keep the middle character aside for odd-length string and check the start and end parts of the string to see if the start half needs incrementing or whether the reversed start is good enough to get the next palindrome. If you need to increment, first option is the middle character if any, then increment the start character by character, taking care of the all-nines case if appropriate.