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
[edit: link to code]