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.
Your algorithm is O(N^3 logN) though because sorting takes O(NlogN) time. You can imporve it like this.
fromcollectionsimportCounterdefcount_anagrams(string):buckets={}foriinrange(len(string)):forjinrange(1,len(string)-i+1):key=frozenset(Counter(string[i:i+j]).items())# O(N) time key extractbuckets[key]=buckets.get(key,0)+1count=0forkeyinbuckets:count+=buckets[key]*(buckets[key]-1)//2returncount
I tested this and it runs much faster on larger inputs.
Sherlock and Anagrams
You are viewing a single comment's thread. Return to all comments →
Your algorithm is O(N^3 logN) though because sorting takes O(NlogN) time. You can imporve it like this.
I tested this and it runs much faster on larger inputs.