The key to understanding the rest of the implementation is this pseudocode:

1for start + distance = end, str[start, end] will be palindromic
2if str[start] == str[end]
3and
4str[start + 1, end - 1] (the "inner" part of the string) is palindromic 

What we're doing is moving "inwards" at each step, so we do start + 1 and end - 1. It also means we can use this state transition equation:

1state(start, end) is true if:
2for start = end, 
3for start + 1 = end,  if str[start] == str[end]
4for start + 2 <= end, if str[start] == str[end] && state(start + 1, end - 1) is true

The time complexity of this program is O(n^2) as the time complexity for creating the table is O(n*2). For traversing and filling the table it is O(n^2) as well, and thus reduces to an O(n^2) solution.

In this solution, we are creating a table of size n*n. So the space complexity will also be O(n^2).

The maxLen variable keeps track of the longest palindromic substring and output has stored the longest palindromic string found so far. In the end, the function returns the output i.e the longest palindromic substring.

xxxxxxxxxx

def longestPalindromicString(string: str) -> str:

    length = len(string)

    table = [[False] * length for _ in range(length)]

    output = ""

​

    for i in range(length):

        table[i][i] = True

        output = string[i]

​

    maxLen = 1

    for start in range(length - 1, -1, -1):

        for end in range(start + 1, length):

            if string[start] == string[end]:

                if end - start == 1 or table[start + 1][end - 1]:

                    table[start][end] = True

                    if maxLen < end - start + 1:

                        maxLen = end - start + 1

                        output = string[start : end + 1]

    return output

​

print(longestPalindromicString('algoog'))