# Finding time complexity of my solution to the 'longest palindrome' problem in Python

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[0]

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.

Long version:

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[0]

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).

• Welcome to Code Review! When you have two versions of a program, as here, we'd prefer you to pick the one you think is best. (Reviewing two versions is more than twice the work, so you'll get better answers with just one version.) – Gareth Rees May 21 '18 at 7:30
• I might be wrong but i think the reverse string function is raising it to n^3 since you are doing an O(n) every n^2 – Mixone May 21 '18 at 7:37

1. Use at least one linter like pycodestyle on your code to learn to write more idiomatic Python. This makes the code easier to read for other Python developers.
2. Most of the names are good (longestPalindrome), but
1. index, i and findcharIndex in a single method is very confusing,
2. the semantics of A, oList, j and Solution all have to be inferred from context which is mentally taxing, and
3. type suffixes like in remString are generally discouraged.
3. if foo then return true else return false should be replaced with simply return foo in any language.
4. Ideally your algorithm should not need the if(longestPalindrome == ""): check at the end - longestPalindrome should contain the longest palindrome by then.
5. Many @staticmethods is a common anti-pattern indicating that the code is really imperative rather than object oriented. This code might work better as a @property of str, since semantically that is what it is.