r/pythonhelp • u/HeadTea • 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 currentLongestI'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