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.
xxxxxxxxxx20
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 outputOUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
