CODEWITHSUNDEEP
pythonoptimization
Fiction Free
Fiction Free

Reputation: 55

Python optimizing loops for checking number of anagrams

i am trying to solve a question that provides a string as input and gives the number of anagrams possible as output. this can be solved using dictionaries but i could only think in terms of for loops and string indices. 

count = 0
    for i in range(1,len(s)):
        for j in range(0,len(s)):
            for k in range(j+1,len(s)):
                if(k+i>len(s)):
                    continue
                # print(list(s[j:j+i]),list(s[k:k+i]),j,j+i,k,k+i)
                if(sorted(list(s[j:j+i]))==sorted(list(s[k:k+i]))):
                    count +=1         
    return count

i have coded this far and tried for optimization with k+i. can someone tell me other techniques to optimize the code without losing the logic. the code keeps getting terminated due to time-out for larger strings.should i replace sorted function with something else.

Upvotes: 0

Views: 117

Answers (1)

augray
augray

Reputation: 3161

The number of anagrams if each letter was unique would be n! with n as the length of the string (e.g. law has 3!=6). If there a given letter is repeated, say, twice (e.g. wall), then you have twice as many answers as you should (since things like w-(second l)-(first l)-a are actually indistinguishable from things like w-(first l)-(second l)-a). It turns out that if a letter is repeated k times (k is 2 for the letter "l" in wall), n! overcounts by a factor of k!. This is true for each repeated letter.

So to get the number of anagrams, you can do:

letter_counts = get_letter_counts(s) #returns something like [1, 1, 2] when given wall, since there is one w, one a, two ls
n_anagrams = factorial(len(s))

#account for overcounts
for letter_count in letter_counts:
    n_anagrams /= factorial(letter_count)

return n_anagrams

Implementing factorial and get_letter_counts left as an excercise for the reader :-) . Note: Be careful to consider that repeated letters can show up more than once, and not always next to each other. Ex: "aardvark" should return a count of 3 for the "a"s, 2 for the "r"s, and 1 for everything else.

Upvotes: 2

Related Questions