r/pythonhelp • • Jan 03 '23

Time complexity of this code

I did the following LeetCode question and this is my solution:

class Solution:
    def longestPalindrome(self, s: str) -> str:
        hashmap = {}
        
        # Create a dictionary that shows in what locations a letter appears
        # So for "abca" it will be: {a:[0,4],b:[1],c:[2]}
        for i,c in enumerate(s):
            if c in hashmap:
                hashmap[c].append(i)
            else:
                hashmap[c] = []
                hashmap[c].append(i)
         
        # For each letter that appears more than once, check if it's a palindrome from first to last occurance
        max = 0
        for c,l in hashmap.items():
            if len(l) > 1:
                for i in range(len(l)):
                    for j in range(i+1,len(l)):
                        partial = s[l[i]:l[j]+1]
                        #print(partial)
                        if partial == partial[::-1] and len(partial) > max:
                            max = len(partial)
                            currentLongest = partial
        if max == 0:
            return s[0]
        else:
            return currentLongest

I'm trying to learn the Time complexity but I'm struggling to understand what is the time complexity of this code. Is it O(n3)? Thanks ahead!

3 Upvotes

0 comments sorted by