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.
I am stuck for a long time too, and hopefully it's still useful for you and anyone else. If I got any of this wrong please feel free to correct me.
Basically, the weirdness of the problem comes in that it asks for anagram pairs, not the commonly-understood meaning of anagrams -- in the example given, kkk[...] contains the anagram pairs [0, 1], [1, 2], etc. even though they are all ["k" "k"]. In the other words, we are merely looking for unique combinations, not unique words.
With that in mind, let's work through the example:
kkkk
The first iteration is trivial: you get [“k”, “kk”, “kkk”, “kkkk”] (indices {0}, {0, 1}, {0, 1, 2}, {0, 1, 2, 3}) in the map, all with value = 1, and total count = 0 so far.
The second iteration is also simple: you get [“k, “kk”, “kkk”] (indices [{1}, {1, 2}, {1, 2, 3}, and adding these will result in the map having value = 2 for these three combos, and total is now 3 (1+1+1, or [k, k], [kk, kk], [kkk, kkk] in indices [{0}, {1}], [{0, 1}, {1, 2}], [{0, 1, 2}, {1, 2, 3}] )
The third is where it starts getting tricky. You get [“k”, “kk”] (indices [{2}, {2, 3}]. Adding these to the map results in the map having value = 3, but what should total be?
You are looking for the pairs [k] (indices [{0}, {2}], [{1}, {2}]) — total += 2
and pairs [kk, kk] (indices [{0, 1}, {1, 2}] and [{0, 2}, {1, 2}], — total += 2
See how total is not just +1 for every pair you found, but +2 instead? That’s because for every pair you found, it can now combine with an previously found anagram for form a new anagram, i.e., you can add anagrams to form new anagrams.
If you are looking for a pattern, the amount added to the total for each match is not merely 1, but the number of matches found already - in this case, it’s +2 instead of just +1.
To finish off, the last iteration: [k] — k’s value in map is now 4, and total += 3 because the pair [{0}, {3}], [{1}, {3}], [{2}, {3}]
Now, if you sum the totalValues after each iteration, it will be 0 + 3 + 4 + 3 = 10, as expected. If you exact the pairs, it is indices:
[{0}, {1}] [{0, 1}, {1, 2}] [{0, 1, 2} {1, 2, 3}] — found in second iteration
[{0}, {2}] [{1}, {2}], [{0, 1}, {1, 2}] [{0, 2}, {1, 2}] — found in the third iteration
[{0}, {3}] {{1}, {3}], [{2}, {3}] — found in the forth iteration.
I hope this explanation helps. This solution is brilliant and I wish I could come up with it myself =)
Sherlock and Anagrams
You are viewing a single comment's thread. Return to all comments →
I am stuck for a long time too, and hopefully it's still useful for you and anyone else. If I got any of this wrong please feel free to correct me.
Basically, the weirdness of the problem comes in that it asks for anagram pairs, not the commonly-understood meaning of anagrams -- in the example given, kkk[...] contains the anagram pairs [0, 1], [1, 2], etc. even though they are all ["k" "k"]. In the other words, we are merely looking for unique combinations, not unique words.
With that in mind, let's work through the example:
kkkk
The first iteration is trivial: you get [“k”, “kk”, “kkk”, “kkkk”] (indices {0}, {0, 1}, {0, 1, 2}, {0, 1, 2, 3}) in the map, all with value = 1, and total count = 0 so far. The second iteration is also simple: you get [“k, “kk”, “kkk”] (indices [{1}, {1, 2}, {1, 2, 3}, and adding these will result in the map having value = 2 for these three combos, and total is now 3 (1+1+1, or [k, k], [kk, kk], [kkk, kkk] in indices [{0}, {1}], [{0, 1}, {1, 2}], [{0, 1, 2}, {1, 2, 3}] ) The third is where it starts getting tricky. You get [“k”, “kk”] (indices [{2}, {2, 3}]. Adding these to the map results in the map having value = 3, but what should total be?
You are looking for the pairs [k] (indices [{0}, {2}], [{1}, {2}]) — total += 2 and pairs [kk, kk] (indices [{0, 1}, {1, 2}] and [{0, 2}, {1, 2}], — total += 2
See how total is not just +1 for every pair you found, but +2 instead? That’s because for every pair you found, it can now combine with an previously found anagram for form a new anagram, i.e., you can add anagrams to form new anagrams.
If you are looking for a pattern, the amount added to the total for each match is not merely 1, but the number of matches found already - in this case, it’s +2 instead of just +1.
To finish off, the last iteration: [k] — k’s value in map is now 4, and total += 3 because the pair [{0}, {3}], [{1}, {3}], [{2}, {3}]
Now, if you sum the totalValues after each iteration, it will be 0 + 3 + 4 + 3 = 10, as expected. If you exact the pairs, it is indices: [{0}, {1}] [{0, 1}, {1, 2}] [{0, 1, 2} {1, 2, 3}] — found in second iteration [{0}, {2}] [{1}, {2}], [{0, 1}, {1, 2}] [{0, 2}, {1, 2}] — found in the third iteration [{0}, {3}] {{1}, {3}], [{2}, {3}] — found in the forth iteration.
I hope this explanation helps. This solution is brilliant and I wish I could come up with it myself =)