0
\$\begingroup\$

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

\$\endgroup\$
  • 4
    \$\begingroup\$ 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.) \$\endgroup\$ – Gareth Rees May 21 '18 at 7:30
  • \$\begingroup\$ 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 \$\endgroup\$ – Mixone May 21 '18 at 7:37
3
\$\begingroup\$

Some thoughts on the long version only:

  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.
\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.