DCP46 - Longest palindrome substring

'''
This problem was asked by Amazon.
Given a string, find the longest palindromic contiguous substring. If there are more than one with the maximum length, return any one.
For example, the longest palindromic substring of "aabcdcb" is "bcdcb". The longest palindromic substring of "bananas" is "anana".
'''

# 1st Function
def isPalindrome(word):
    n = len(word)
    if n == 1:
        # A word with 1 letter cannot be a palindrome
        return False
    flag = True
    for i in range(int(n/2)):
        if word[i] != word[n - 1 - i]:
             flag = False
             break
    return flag

# 2nd Function
def longestPalindrome(messageWord):
    n = len(messageWord)
    flag = False
    if isPalindrome(messageWord):
        flag = True
        return messageWord
    # Now, I will search for "consecutive" substrings that are maybe palindromes
    for LENGTH in range(n-1, 0, -1):
        # We speak about substrings with length = LENGTH
        # If my word has 7 letters, I look 2 substrings with LENGTH = 6, 3 substrings with LENGTH = 5 etc
        for firstIndex in range(0, n+1 - LENGTH):
            word = messageWord[firstIndex : firstIndex+LENGTH]
            if isPalindrome(word):
                flag = True
                return word
    if flag == False:
        return ("The word '" + str(messageWord) + "' does not contain any palindrome")


# 3rd Function
def prettyPrint(messageWord):
    answer = longestPalindrome(messageWord)
    print(str(messageWord) + " ----> longest palindrome substring = " + str(answer))

# MAIN FUNCTION
messageWords = ["bananas", "banana", "anana", "Anana", "Saab", "aara", "BB", "cb", "c"]
for messageWord in messageWords:
    prettyPrint(messageWord)