AlgoDaily - Longest Palindromic Substring

The time complexity for this function will be O(n*3), as the complexity to find all possible strings is O(n*2) and the one to check if it's a palindrome is O(n). This results in O(n2*n)= O(n3).

Is there a better, more efficient method to solve this problem?

Of course! There are many solutions to a problem if we'll look hard enough for them. We will share another solution with you that will use the dynamic programming technique to find the longest palindromic substring.

xxxxxxxxxx
 
def longestPalindromicString(string: str) -> str:
    if len(string) < 2:
        return string
​
    if len(string) == 2:
        if string == string[::-1]:
            return string
        return string[0]
​
    output = ""
    for i in range(len(string)):
        for j in range(len(string) - 1, i, -1):
            if string[i : j + 1] == string[i : j + 1][::-1]:
                if len(output) < len(string[i : j + 1]):
                    output = string[i : j + 1]
​
    if not output:
        return string[1]
​
    return output

OUTPUT

Results will appear here.