Is Anagram?

 Today's AlgoDaily problem is determining if two strings are anagrams, meaning strings that have the same characters in exactly the same proportions, but permuted.

I first thought, do a linear scan through the second string, store the letters in a hash table and then scan through the first string and check whether the letter appears in the hash table. But then I thought there would be repeated letters so it wouldn't work (it actually would! read on!). Two for loops O(n**2) solution-- scanning over both of the strings wouldn't work for exactly the same reason. You need to count the letters. At that point I peeked at the solution and wow! You can do it in O(n*log(n)) if you sort both the strings and simply check for equality. 

But when I coded up the second solution I realized that my initial intuition is correct and would give O(n) complexity. What you do is to build two hash tables for each string. You scan them linearly and keep the counts of the letters as values and the letters themselves as keys. You update the value each time you see the letter in the hash table again! Then you extract the keys of one of the dictionaries and loop through them doing a O(1) operation in the second hash table and compare the counts. If at any point you encounter a different count you break, if you made it to the end of the list you're golden. Now the tricky part, it's like an mathematical equivalence proof. You have to show both directions of the implication to have an equivalence. So you now have to take the second string and do the same thing, taking it as a reference and checking the first string's hash table. If you don't like this complicated mathematical stuff, just check that the length of the strings is the same:-D

The complexity of my solution is O(n) because building each hash table is linear and the linear passes through them is also O(n), because a hash table lookup is O(1). So O(4*n), but you can drop the constant factors;-)

The code is here: https://github.com/mariakesa/Algorithms/blob/master/AlgoDaily/AlgorithmsPractice.ipynb

I love these daily exercises!