0
\$\begingroup\$

I have encountered to this question and applied a brute force algorithm off top of my head and couldn't find a better optimized solution.

I was hoping I could get some insight to implement a better optimized code in terms of complexity. My solution has \$O(n^2)\$ time and space complexity.

class Solution:

    def longestPalindrome(self, s: 'str') -> 'str':
        if s=="":
            return ""
        else:
           ## Find all the substrings
            arr=[]
            for i in range(len(s)):
                char = s[i]
                arr.append(char)
                for j in range(i+1, len(s)-1):
                    char+=s[j]
                    arr.append(char)

            ##Find the palindrome with a longest length
            max_length = 0
            for j in range(len(arr)):
                if self.isPalindrome(arr[j]):
                    if len(arr[j]) > max_length:
                        max_length = len(arr[j])
                        index = arr[j]
            return index


    def isPalindrome(self,s:'str')->'str':
        if s == s[::-1]:
            return True
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.