Longest Palindromic Substring

lpsub.py

def longest_palindrome_constant_space(s):

    N = len(s)

    if N == 0:
        return 0
    elif N == 1:
        return 1
    elif N == 2:
        return 1 + (s[0] == s[1])

    def length(s, beg, end):
        while 0 <= beg and end < len(s) and s[beg] == s[end]:
            beg, end = beg - 1, end + 1
        return end - beg - 1

    max_even = max(length(s, k - 1, k + 1) for k in range(1, N))
    max_odd  = max(length(s, k, k + 1) for k in range(1, N))

    return max(max_even, max_odd)

def is_palindrome(s, n, m):
    return (n == m or
            (s[n] == s[m] and
             (n + 1 == m or
              is_palindrome(s, n + 1, m - 1))))

def lps(s):
    """Longest palindromic substring"""
    def is_palindrome_internal(s, n, m):
        if n == m:
            return True
        elif (n + 1 == m):
            return s[n] == s[m]
        elif s[n] == s[m]:
            return is_palindrome_internal(s, n + 1, m - 1)
        else:
            return False

    def longest(s):
        beg    = None
        end    = None
        length = 0
        for n in range(len(s)):
            for m in range(n, len(s)):
                if is_palindrome(s, n, m):
                    if m - n + 1 > length:
                        length = m - n + 1
                        beg = n
                        end = m + 1
        return (length, beg, end)

    length, beg, end = longest(s)
    lpcs = longest_palindrome_constant_space(s) # for comparison
    print(f"{s[0:beg]}[{s[beg:end]}]{s[end:]}")
    if lpcs > 0:
        print(" " * (beg + 1),
              "*" * (end - beg),
              f" [length: {lpcs}]",
              sep="")

lps("ANNAHANANAHBANANA")
lps("B")
lps("BOB")
lps("BANANAINHAVANA")
lps("")
lps("XY")
lps("AA")
lps("MROWLATEMYMETALWORM") # MR. OWL ATE MY METAL WORM
lps("AMANAPLANACANALPANAMA") # A MAN, A PLAN, A CANAL -- PANAMA
lps("ABBA")
lps("ABC")

Sample output

ANNA[HANANAH]BANANA
     ******* [length: 7]
[B]
 * [length: 1]
[BOB]
 *** [length: 3]
B[ANANA]INHAVANA
  ***** [length: 5]
[]
[X]Y
 * [length: 1]
[AA]
 ** [length: 2]
[MROWLATEMYMETALWORM]
 ******************* [length: 19]
[AMANAPLANACANALPANAMA]
 ********************* [length: 21]
[ABBA]
 **** [length: 4]
[A]BC
 * [length: 1]