We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Hey, 1 improvement that can be made that changes the runtime from O(n^3) to O(n^2), essentially removing the highest-nested for loop. my code:
defstrhash(s):h=0forcins:h+=hash(c)return(h)defseqsum(n):returnint((n**2+n)/2)defsherlockAndAnagrams(s):count=0forlinrange(len(s)):counter=dict()#l is length of substr.foriinrange(len(s)-l):hashed=strhash(s[i:i+l+1])ifhashednotincounter:counter[hashed]=1else:counter[hashed]+=1fork,vincounter.items():ifv>1:count+=seqsum(v-1)print(count)returncount
Additional comment about my code, I know it assumes it won't encounter any strhash collisions (: but it passed all the tests
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Sherlock and Anagrams
You are viewing a single comment's thread. Return to all comments →
Hey, 1 improvement that can be made that changes the runtime from O(n^3) to O(n^2), essentially removing the highest-nested
for
loop. my code:Additional comment about my code, I know it assumes it won't encounter any strhash collisions (: but it passed all the tests