I doubt that the interviewer mentioned the prime number solution due to insufficient cleverness in the original solution. The answered O(n+m) solution actually

I doubt that the interviewer mentioned the prime number solution due to insufficient cleverness in the original solution. The answered O(n+m) solution actually contains flaws beyond its lack of cleverness. 1) there's no good reason to use a hash map, hashing is useful in maps for mapping an unevenly distributed set from a large an arbitrarily large space to an evenly distributed set from an arbitrarily small space. The space is only 26 characters so why hash? You can simply use a map (no hash needed), and in this case there's even a very natural way to get indices into an array (index(c) = c - 'a'). Now it's true, that these are both linear time solutions simply with different factors and we might simply say who cares. The thing about the prime solution is that it's actually really dumb itself and I think that's what Guy really wanted you to tell him. He was pointing out that you could leverage the smallness of your data and hoping the interviewee would come up with an even better way to leverage this fact. The first thing we should notice is that asymptotic bounds are misplaced here if you consider how such a function might actually be used. The strings are basically being used as sets that is AA might as well be A as far as our answer is concerned. So assuming people aren't giving us stupid data (and in an interview you could mention a way to make this assumption true). The strings shouldn't ever have duplicates and thus shouldn't ever be bigger than 26 characters (otherwise they contain all of the characters and the answer is independent). So if a solution has runtime n + m + c, that c actually starts to matter. The thing about the primes solution is that multiplication and modulo operations are actually very expensive and all you want to keep track of is whether you've seen a character (1 bit of information) so you should really use a bitmap for this. And since it so happens that 26 < 32 these will fit very nicely in a single int. It's even a pretty nice implementation: https://gist.github.com/707639 https://gist.github.com/707639 [edit: link to code]