Find longest palindromic substring using Python

  • A palindrome is a word, number or phrase which is same when read from left to right or right to left.

    Examples:
    Rotor, Ava, Salas
    top spot

    1001, 12321, 111

    A string or phrase can have one or more palindromes within as well. In this topic, we will try to find the longest palindrome within a string.

    As an example a word potatopot is not a palindrome in itself. But it has 2 palindromes within; topot and potatop. If we are looking for the longest palindrome, output should be potatop, which is of 7 letters.

  • Below code finds the longest palindrome within a string.

    Logic here is to loop through each character in the string and find equal length characters around it and check if it is palindrome. If the check satisfies, radius increases, till we find the largest palindrome around a character.

    Then go to the next character and if it has a longer palindrome, this gets stored in the finalCenter and finalRadius variables.

    Example: POPCBABCD
    When loop reaches character O, finalCenter = 1 , finalRadius = 1
    and longestpalin = POP

    When it reaches character A, finalCenter = 5 , finalRadius = 2
    and longestpalin = CBABC

    This logic works fine, if the palindromes within are of odd length. But will not work for palindromes of even length. To overcome this, we are inserting a special character (Any character can be used, which has the least chance of occurring in our string) in between each character and at the start and end also. In this sample we are using @

    Examples:
    ABC becomes @A@B@C@ (Length = 7).
    AB becomes @A@B@ (Length = 5).

    Copied 
    str1 = 'potatopot'
spStr = '@'

for c in list(str1):
    spStr = spStr + c + '@'
strlength = len(spStr)

finalCenter = 0
finalRadius = 0

for c in range(0, strlength):
    rad = 0
    while c - (rad+1) >= 0 and c + (rad+1) < strlength and spStr[c-(rad+1)] == spStr[c+(rad+1)]:
        rad = rad+1

    if(rad > finalRadius):
        finalCenter = c
        finalRadius = rad

longestpalin = spStr[ finalCenter - finalRadius : finalCenter + finalRadius + 1 ]
longestpalin = longestpalin.replace('@', '')

print("Longest Palindrome is: " + longestpalin)
    Output:
      Longest Palindrome is: potatop
Absolute Code Works - Python Topics