Here is a short version!
def longestPalindrome(string): # Will use this string to record the longest palindrome seen so far largestPalindrome = "" for index in range(0, len(string)): reqcharMatch = string[index] # Since a palindrome must have matching start and end characters # I will find the index of all occurrences of the current # character that I'm looking at in the remaining string. # Will accomplish this using regular expression or simply # by passing the character I'm looking to find, the remaining # string to another function, it will return a list having # indices where matching character is present. # Let us for example assume that, the character I'm at currently # is also present in indices 4, 8, 9. # otheroccurList = [4, 8, 9] otheroccurList = regexFunctionHere() for occurrenceIndex in range(len(otheroccurList)): originalString = string[index: otheroccurList[occurrenceIndex] + 1] reversedString = originalString[::-1] # If the string obtained by slicing from the current # character to the next occurence of the same character is # a palindrome, and the length of this particular string is # more than the largestPalindrome seen so far, then update # largestPalindrome to be equal to the current Palindrome # we are looking at. if((reversedString == originalString) and (len(originalString) >= largestPalindrome)): largestPalindrome = originalString # If literally no palindrome is found, then simply return the # first character in the string if largestPalindrome == "": return string else: return largestPalindrome
Here is a longer version, please forgive me if its not refactored. I did my best to ensure good variable names, but you can copy paste this and run it with whatever test cases, it will pass them.
class Solution: @staticmethod def findallOccurrence(findcharIndex, chartoFind, remString): """ Function to find the all other indices where a character appears. """ occurrenceList =  for i in range(len(remString)): if(remString[i] == chartoFind): index = findcharIndex + i + 1 occurrenceList.append(index) index = 0 return occurrenceList @staticmethod def reverseString(origString): """ Function to reverse a string """ return origString[::-1] @staticmethod def checkPalindrome(origString, reversedString): """ Function to check if the original string and the reversed string is a palindrome. """ if(origString == reversedString): return True else: return False def longestPalindrome(self, A): """ This is my main function whose short version I've explained. """ longestPalindrome = "" for index in range(len(A)): findChar = A[index] remainingString = A[index + 1:] oList = findallOccurrence(index, findChar, remainingString) for j in range(len(oList)): origString = A[index: oList[j] + 1] revString = reverseString(origString) isPalindrome = checkPalindrome(origString, revString) if(isPalindrome == True) and (len(origString) >= len(longestPalindrome)): longestPalindrome = origString if(longestPalindrome == ""): return A else: return longestPalindrome sol1 = Solution() sol1.longestPalindrome("abaaaaaa")
The reason I'm having trouble finding the time complexity of my solution is that there are many interlinked loops, and different function calls within them.. I think its O(n^2), but it looks like its O(n^3).