Fast anagram solving

Question

Given two strings, I would like to determine whether or not they are anagrams of one another. Here is the solution that I came up with:

# output messages
def anagram
    puts "Anagram!"
    exit 
end

def not_anagram
    puts "Not an anagram!"
    exit
end

# main method
if __FILE__ == $0
   # read two strings from the command line
   first, second = gets.chomp, gets.chomp

   # special case 1
   not_anagram if first.length != second.length

   # special case 2
   anagram if first == second

   # general case
   # Two strings must have the exact same number of characters in the
   # correct case to be anagrams.
   # We can sort both strings and compare the results
   if first.chars.sort.join == second.chars.sort.join
      anagram
   else
      not_anagram
   end
end

But I am thinking that there is probably a better one. I analyzed the efficiency of this solution, and came up with:

• chars: splits a string into an array of characters O(n)
• sort: sorts a string alphabetically, I don't know how sort is implemented in Ruby but I assumed O(n log n) since that is the generally best known sorting efficiency
• join: builds a string from an array of characters O(n)
• ==: The string comparison itself will have to examine every character of the strings 2*O(n)

Given the above, I categorized the efficiency of the entire solution as O(n log n) since sorting had the highest efficiency. Is there a better way to do this that is more efficient than O(n log n)?

Answer 1

Your big O should be O(n*lg(n)) since the sort is the limiting function. If you try it with very big anagrams you will see a loss of performance higher than expected for an O(n) solution.

You can do an O(n) solution by comparing counts in two maps of characters => character counts.

There are definitely other solutions that work with approximately the same complexity but I don't think you can come up with anything faster than O(n)