Finding the Longest Palindromic Substring using Dynamic Programming in O(n^2) time complexity

LPS : Dynamic Programming.py

def longest_palindromic_substring(string):
    length = len(string)

    # return the string if the string is only one character long
    if length == 1:
        return string

    palindrome = ""
    palindrome_length = 0

    # initialise the dp array and set all to false
    dp = [[False for i in range(length)] for j in range(length)]
    
    # set the diagonal to true as every single character is a palindrome
    for i in range(length):
        dp[i][i] = True

    '''
           0 1 2 3 4    
        0  T F F F F
        1  F T F F F
        2  F F T F F
        3  F F F T F
        4  F F F F T
    '''
    
    # only need to check the top right triangle
    # 01 12 23 34 -> difference = 1
    # 02 13 24    -> difference = 2
    # 03 14       -> difference = 3
    # 04          -> difference = 4
    # keep on varying difference from 1 to length-1 and traverse each diagonals
    
    for x in range(1,length):
        i = 0
        j = i + x

        while j < length:
            # for 2 characters just check if the characters are same
            if x == 1:
                if string[i] == string[j]:
                    dp[i][j] = True
            # for the rest look at the bottom left cell and the first and last characters
            # the bottom left cell tells if the characters in the middle form a palindrome or not
            else:
                if string[i] == string[j] and dp[i+1][j-1] == True:
                    dp[i][j] = True

            # if the cells are updated to true at any point update the palindrome
            if dp[i][j]:
                if len(string[i:j+1]) > palindrome_length:
                    palindrome = string[i:j+1]
                    palindrome_length = len(string[i:j+1])
                    
            # update values for next iteration
            i += 1
            j = i + x

    # if no palindrome is found return the first character itself
    if palindrome_length == 0:
        return string[0]
    else:
        return palindrome