CareerCup

public boolean anagrams(String a, String b)
{
if(a.length()!=b.length())
{
return false;
}
int [] letter=new int[256]; //assumption that character set was ASCII
char[] tmp=a.toCharArray();
for(char c:temp)
{
letter[c]++;
}
for(int i=0;i<b.length();i++)
{
int c=(int)b.charAt(i);
if(--letter[c]<0)
{
return false;
}
}
return true;
}

1.sort the both string and in one loop compare each character, if each character matches, then both strings are anagram of each other. Time Complexity O(nlogn), Space complexity O(1)
2. Create a hashmap with key as character and value as counter. Traverse the first string and insert character in map if it does not exist, otherwise increment the counter.
Now, for second string, loop through each character, and search in the map and if any character does not exist, then return false, if exists then reduce the value of that key. once looping over second string is over, iterate through hashmap and all values stored in the map should be zero. then return true, otherwise return false.

psudo code:

bool isAnagram(char *str1, char *str2)
{
if (strlen(st1) != strlen(str2))
return false;
int charIndex[256] = {0};
int i = 0;
while (*str1 != '\0') {
charIndex[*str1] += 1;
charIndex[*str2] -= 1;
str1++, str2++;
}
while (i < 256) {
if (charIndex[i] != 0) {
return false;
}
i++;
}
return true;
}

what about the next algo

char sum = 0;
for(int i = 0;i < strlen(s1);i++) {
	sum += (s1[i] ^  s2[i]);
}

if(sum == 0 )
	return true;
else 
return false;

So if s1 is just only permutation of s2 characters it meants that each symbol c1 in s1 has equal in s2. So c1 xor c2 == 0.

1. Check if the lengths are same. If so, continue to step 2, else return false.
2. Insert each character of first string into std::set<char>. This is C++ specific. Other languages might be having counterpart of set.
3. Iterate through each character of second string and do a std::set::find on the set created in step 2.
4. If std::set::find returns std::set::end at any time during iteration, then result is false and break the loop. Else return true.

Complexity nlogn

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int main()
{ int z=0,y=0,c=0,p,i,q;
char s1[]="ram is going to agra";
char s2[]="agra to going is ram";
if((q=strlen(s1))!=strlen(s2))
{printf("false");
}
p=q-1;
for(i=0;i<p;i++)
{
z+=s1[i];
y+=s2[p-i];
printf("%d, %d\n",z,y);
if((s1[i]==' '&&s2[p-i]==' '))
{ c++;
if(z==y)
{ c--;}
z=0;
y=0;
}
}
printf("%d",c);
if(c==0)
{printf("string is panagram");}
else{printf("not");}
system("pause");
}

The most efficient algo is actually going to depend on the size of your character set relative to the size of the string, there is a way to do it in O(n) time with O(1) space(much less than a hash map), you simply use the concept of "buckets", here is the code in Java:

import static org.junit.Assert.*;

import org.junit.Test;


public class AnagramFinder {

	public static boolean areAnagrams(String s1, String s2) {
		if(s1.length() != s2.length())
			return false;
		//Assume ascii set
		int[] s1Counts=new int[256];
		int[] s2Counts=new int[256];
		
		for(int i=0;i<s1.length();i++) {
			s1Counts[s1.charAt(i)]++;
			s2Counts[s2.charAt(i)]++;
		}
		
		for(int i=0;i<s1Counts.length;i++) {
			if(s1Counts[i] != s2Counts[i])
				return false;
		}
		return true;
	}
	
	@Test
	public void testAreAnagrams() {
		assertTrue(areAnagrams("that","hatt"));
	}
	@Test
	public void testNotAnagrams() {
		assertFalse(areAnagrams("that","hart"));

	}
	
}

This is faster and takes less space than the hashmap(though both are O(n) time and O(1) space, in practice the above is faster), but this tends to fall apart if you have larger char sets.

Another even less practical(though more space efficient) method is to assign each letter a prime value('a' is 2, 'b' is 3, 'c' is 5 etc) then multiply all those together. This just requires 2 BigNumber objects(and a lookaside table to translate the characters into their primes)....theoretically if you had to calculate a lot of anagrams simultaneously with a large ROM but very little RAM you could use that method, but somehow I doubt that's really practical :P