Find if 2 strings are anagram in O(1) space and O(n) time

Question

You can find if 2 strings are anagrams after sorting both strings in O(nlogn) time, however is it possible to find it in o(n) time and O(1) space.

Answer 1

---

There are couple of ways to solve it.

Method 1 - Using custom hash code function
We can have hashCode function like:

static int[] primes = {3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103};
static String alphabet = "abcdefghijklmnopqrstuvwxyz";


public static int hashCode(String s){
    int sum = 0;

    for(char c: s.toCharArray()){
      sum += primes[c-97];
    }
    return sum;
}

Generate the hash of both strings, and if the hashCode are equal strings are anagrams. This method is similar to solution mentioned by Jin, as it is in some way generating hashCode for string.
Time complexity - O(n)

Method 2 - Use hashmap of Character and Integer
Consider 2 strings as 2 arrays of character. Traverse first array, add the character to hashmap of char and count, increment the count when you find the character. Likewise traverse through second array, decrement the counter in the hashmap, or if you dont find the character, they are not anagrams. Finally, when map has all the characters and count as 0, then again 2 strings are anagrams.

Method 3 - Use a count array(my favourite)

boolean are_anagrams(string1, string2){
 
    let counts = new int[26];
 
    for each char c in lower_case(string1)
        counts[(int)c]++
 
    for each char c in lower_case(string2)
        counts[(int)c]--
 
    for each int count in counts
        if count != 0
            return false
 
    return true
}

You can get all the codes here.

Answer 2

Absolutely no expert here...

But why not go through each string and simply count how many times each letter turns up.

Given appropriate implementation, this shouldn't take more than O(n) time.