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

generate a prime number array[26] each prime number represent a character, then when you traverse the string, multiple each character's prime number, if equal, it is anagrams, otherwise not. it takes O(n) and constant space

Answer 3

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.

Answer 4

Yes, use a hash and count occurences. If at the end, we have a non-zero figure, then the strings are not anagrams.

let h => hash which maps letters to occurence_count (initialized to 0)

for each letter l in string a
  h[l] = h[l] + 1
end

for each letter l in string b
  h[l] = h[l] - 1
end

for each key l in h 
  return false if h[l] != 0
end

return true

This will run in O(n) + O(n) + c = O(n). Our hash contains 26-letter spots, each with an integer associated with it. The space is therefore O(26) = O(1)

[[Edit]], same as above, but with time-analysis annotations:

let h => hash which maps letters to occurence_count (initialized to 0)

#this loop runs n times
for each letter l in string a
  #hash lookups / writes are constant time
  h[l] = h[l] + 1
end
#above function ran O(n) time

for each letter l in string b
  h[l] = h[l] - 1
end

#runs in O(alphabet) = O(c) = constant-time
for each key l in h 
  return false if h[l] != 0
end

return true

Answer 5

Run in : O(n) + O(n) = O(n)

Fix Used Space : O(256) = O(1)

Here is code in Java

private static boolean isAnagramWithOneArray(String strFirst, String strSecond) {
    int[] charsCount = new int[256];

    if (strFirst != null && strSecond != null) {
        if (strFirst.length() != strSecond.length()) {
            return false;
        }
        for (int i = 0; i < strFirst.length(); i++) {
            charsCount[strFirst.charAt(i)]++;
            charsCount[strSecond.charAt(i)]--;
        }
        for (int i = 0; i < charsCount.length; i++) {
            if (charsCount[i] != 0) {
                return false;
            }
        }
        return true;
    } else {
        return (strFirst == null && strSecond == null);
    }
}

Answer 6

unsigned char CharacterCheck(char item)
{

    if ((item >= 'A') && (item <= 'Z'))
        return (item - 'A');

    if ((item >= 'a') && (item <= 'z'))
        return ((item - ('a' - 'A')) - 'A');

    return -1;

}

unsigned char AnagramCheck6 (char * item1, char * item2)
{
    char *test                      = item1;
    char *test2                     = item2;
    int count                       = 0;
    unsigned char rc                = 0;
    unsigned char rslt              = 0;

    while (*test && *test2)
    {
        rslt = CharacterCheck(*test++);

        if (rslt != 0xff)
            count += rslt;

        rslt = CharacterCheck(*test2++);

        if (rslt != 0xff)
            count -= rslt;
    }

    if (*test)
    {
        while (*test)
        {
            rslt = CharacterCheck(*test++);

            if (rslt != 0xff)
                count += rslt;
        }
    }

    if (*test2)
    {
        while (*test2)
        {
            rslt = CharacterCheck(*test2++);

            if (rslt != 0xff)
                count -= rslt;
        }
    }

    if (count)
        rc = 1;

    return rc;

}

The following snippet checks for the correct character and converts case if needed. The second and third checks takes into account if the strings are different lengths

Answer 7

the above code would fail to work in all condition

rateher we can go for a quick sort and compare the array while elimating spaces

Answer 8

All suggestions here tend to use the same approach of sorting the input strings and then comparing the results. Being mostly interested in regular ascii letters this can be optimized by count sorting which seems to be most answerers approach. Count sort can do sorting of a limited alphabet of numbers / integers in O(n) so technically it is correct answers. If we have to account for the time to traverse the count array afterwards it will include the time for the alphabet, making O(m+n) a somewhat more correct upper bound in cases where the alphabet is UTF-32.

I tend to think the most generally correct approach would require O(n lg n) since a quicksort might prove faster in real time in case the alphabet cannot be limited sufficiently.

Answer 9

i would do it something as below:

//is s an anagram of t?
#include <string>

bool is_anagram(const string& s, const string& t)
    {
    bool ret = false;

    //if s and t are anagrams, they must of same size
    if( s.length() != t.length() )
        {
        return ret;
        }

        //assume that s and t have valid ascii characters only
    char letters[ 256 ] = {0};
    int i;

    // find occurence of each character in string s
    for( i = 0; i < s.length(); i++ )
        {
        (letters[ s[i] ])++;
        }

    // now, find occurence of each character in string t, but decrement 
    // correspnding character
    for( i = 0; i < t.length(); i++ )
        {
        //if the count is <0 means the given character is not present in s
        if( --(letters[ t[i] ]) < 0 ) 
            {
            return ret;
            }
        }

    //out of for loop means success
    ret = true;
    return ret;
    }

Answer 10

If you transform a words characters in sorted order and hash the String. Every String which has the same hash after sorting will be an anagram(very probable, there is always a chance of collisions) of the other.

Answer 11

Something like this using python?

def anagram(a,b):
    s1=list(a)
    s2=list(b)
    for i in s1:
        if i in s2:
            s2.remove(i)
    print(s2)
    return len(s2)==0

This will return false if the strings are not anagram of each other.

To avoid using built ins like remove etc. following approach can be used?

def hana(a,b):
    s1=list(a.lower())
    s2=list(b.lower())
    print(s1,s2)
    h={'a': 0, 'c': 0, 'b': 0, 'e': 0, 'd': 0, 'g': 0, 'f': 0, 'i': 0, 'h': 0, 'k': 0,'j': 0, 'm': 0, 'l': 0, 'o': 0, 'n': 0, 'q': 0, 'p': 0, 's': 0, 'r': 0, 'u': 0, 't': 0, 'w': 0, 'v': 0, 'y': 0, 'x': 0, 'z': 0}
    for i in s1:
        h[i]+=1
    for i in s2:
        h[i]-=1
    for key, val in h.items():
        if val != 0:
            return False
    return(True)

If the strings are anagram of each other then the final hash should have value 0 for all the keys. If its anything other than 0 then we have either repeated characters or characters that are not present in the other string, which means its not anagram.

Answer 12

Maybe something like:

    String str1 = "test";
    String str2 = "tzet";
    int count = 0;
    for (int i = 0; i < str1.length(); i++)
    {
        count = count + str1.charAt(i) - str2.charAt(i);
    }
    System.out.println(count);

Subtract every character from string 2 and add every character from string 1 to count (assuming ASCII characters). If they are anagrams, count will be equal to zero.

This doesn't account for anagrams that have inserted spaces, though.