def longest_palindromic_substring(s):
    # To store the starting and ending indexes of LPS
    res = [0, 0]

    n = len(s)

    # Initialize a lookup table of dimensions len(s) * len(s)
    dp = [[False for i in range(len(s))] for i in range(len(s))]

    # Base case: A string with one letter is always a palindrome
    for i in range(len(s)):
        dp[i][i] = True

    # Base case: Substrings of length 2
    for i in range(len(s)-1):
        dp[i][i + 1] = (s[i] == s[i + 1]) # Check if two characters are equal
        if dp[i][i + 1]:
            res = [i, i + 1] # Update the resultant array

    # Substrings of lengths greater than 2
    for length in range(3, len(s)+1):
        i = 0
        # Checking every possible substring of any specific length
        for j in range(length - 1, len(s)): # Iterate over possible ending indexes
            dp[i][j] = dp[i + 1][j - 1] and (s[i] == s[j])
            if dp[i][j]:
                res = [i, j]
            i += 1
    
    return s[res[0]:res[1] + 1] # Return the longest palindromic substring

# Driver code
def main():
    strings = ['cat', 'lever', 'xyxxyz', 'wwwwwwwwww', 'tattarrattat']
    
    for i in range(len(strings)):
        print(i + 1, ".\t Input string: '", strings[i], "'", sep="")
        result = longest_palindromic_substring(strings[i])
        print("\t Number of palindromic substrings: ", result, sep="")
        print("-" * 100)
    
if __name__ == '__main__':
    main()