CareerCup

Roughly O(nm) complexity and O(nm) memory where n is the number of Strings and m is the length of the Strings.

public static int countAnagramSets(String[] strArr){
    int count = 0;
    HashSet<String> anagramSignatures = new HashSet<String>();
    for(String str : strArr){
        String signature = getSignature(str);
        if(!anagramSignatures.contains(signature)){
            count++;
            anagramSignatures.add(signature);
        }
    }
    return count;
}

private static String getSignature(String str){
    //assuming default character set

    //count each instance of a character in the string
    int[] charCount = new int[26];
    for(char c : str.toCharArray()){
        charCount[(int)c - (int)'a']++;
    }

    //build a suitable signature
    StringBuilder builder = new StringBuilder();
    for(int i = 0; i < charCount.length; i++){
        if(charCount[i] > 0){
            builder.append((char)(i + (int)'a'));
            builder.append(Integer.toString(charCount[i]);
        }
    }
    return builder.toString();
}

Calculate hash of each of the string using a hash functions that does not take the position of character into account. Answer is number of distinct hash values obtained.

Assuming the string has only small case alphabets you can use calculate charCount[26] for each of the string i.e. count of each alphabet considering 'a' is mapped to position 0 in charCount. Answer will be number of distinct charCount arrays generated. Complexity will be O(n*m*26) where n is number of strings, m is string length.

public static int anagramSet(List<String> list){
if(list == null){
return 0;
}
Set<String> set = new HashSet<String>();
for(String str:list){

char[] arr = str.toCharArray();
Arrays.sort(arr);
String sorted = String.valueOf(arr);
set.add(sorted);
}
return set.size();
}

What would be the hash formula in this case?

This might sound silly, but can anyone help me understand
how the original question found 5 sets of anagrams:

Set: <abc,cab,dac,beed,deb,few,acd>
Anagrams:
abc, cab
dac, acd
deb, beed
So 3 sets of anagrams, not 5?

what is the set of anagrams because as per above program the set cantain : a1b1c1,a1c1d1,b1d1e2,b1d1e1,e1f1w1

Ruby impl. Running time: O(n*m*logm). Space:O(n).

require 'set'

def anagrams_count(array)
  return 0 if array.nil? || !array.kind_of?(Array) || array.length == 0
  
  anagrams_set=Set.new
  
  array.each do |str|
    sorted_str=str.chars.sort.join
    anagrams_set.add(sorted_str)
  end
  
  anagrams_set.size
end


require_relative '../../../src/anagrams'

describe 'anagrams' do
  context 'error input: []' do
    let(:strings){[]}
    
    it 'shall return blank' do
      expect(anagrams_count(strings)).to eq(0) 
    end
  end
  
  context 'error input: nil' do
    let(:strings){nil}
    
    it 'shall return blank' do
      expect(anagrams_count(strings)).to eq(0) 
    end
  end
  
  context 'error input: string' do
    let(:strings){'hello'}
    
    it 'shall return blank' do
      expect(anagrams_count(strings)).to eq(0) 
    end
  end
  
  context 'valid input' do
    let(:strings){['abc','cab','dac','beed','deb','few','acd']}
    
    it 'shall return anagrams' do
      expect(anagrams_count(strings)).to eq(5)
    end
  end
end

Explain how is it 5 sets of anagrams?

#include<iostream>
#include<set>
#include<vector>

using namespace std;

int main(){

string collec[] = {"abc","cab","dac","beed","deb","few","acd"};
vector<string> strvec(collec, collec+7);
vector<string>::iterator it = strvec.begin();
set<int> elements;
while(it != strvec.end()){
string input = *it;
int sum=0;
for(string::iterator its=input.begin();its!=input.end();its++){
sum += int(*its);
}
elements.insert(sum);
++it;
}
cout<<"count:"<<elements.size();
}

#include<iostream>
#include<set>
#include<vector>

using namespace std;

int main()

string collec[] = {"abc","cab","dac","beed","deb","few","acd"};
    vector<string> strvec(collec, collec+7);
    vector<string>::iterator it = strvec.begin();
    set<int> elements;
    while(it != strvec.end()){
        string input = *it;
        int sum=0;
        for(string::iterator its=input.begin();its!=input.end();its++){
            sum += int(*its);
            //elements.insert(sum);
        }
        elements.insert(sum);
        ++it;
    }
    cout<<"count:"<<elements.size();
    int c;
    cin>>c;

#include<iostream>
#include<set>
#include<vector>

using namespace std;

int main(){

string collec[] = {"abc","cab","dac","beed","deb","few","acd"};
vector<string> strvec(collec, collec+7);
vector<string>::iterator it = strvec.begin();
set<int> elements;
while(it != strvec.end()){
string input = *it;
int sum=0;
for(string::iterator its=input.begin();its!=input.end();its++){
sum += int(*its);
//elements.insert(sum);
}
elements.insert(sum);
++it;
}
cout<<"count:"<<elements.size();
int c;
cin>>c;
}

#include<iostream>
#include<set>
#include<vector>

using namespace std;

int main(){

string collec[] = {"abc","cab","dac","beed","deb","few","acd"};
vector<string> strvec(collec, collec+7);
vector<string>::iterator it = strvec.begin();
set<int> elements;
while(it != strvec.end()){
string input = *it;
int sum=0;
for(string::iterator its=input.begin();its!=input.end();its++){
sum += int(*its);
//elements.insert(sum);
}
elements.insert(sum);
++it;
}
cout<<"count:"<<elements.size();
int c;
cin>>c;
}

#include<iostream>
#include<set>
#include<vector>

using namespace std;

int main(){

    string collec[] = {"abc","cab","dac","beed","deb","few","acd"};
    vector<string> strvec(collec, collec+7);
    vector<string>::iterator it = strvec.begin();
    set<int> elements;
    while(it != strvec.end()){
        string input = *it;
        int sum=0;
        for(string::iterator its=input.begin();its!=input.end();its++){
            sum += int(*its);
            //elements.insert(sum);
        }
        elements.insert(sum);
        ++it;
    }
    cout<<"count:"<<elements.size();
    int c;
    cin>>c;
}

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <list>
#include <string>
using namespace std;

int main()
{
uint32_t i;
std::string tmp;

std::vector<std::string> str = {"abccd", "efgh", "hytr", "yincec", "ccdba", "cdcba", "yucybd", "hgfe", "ghfe"};
//std::string *str = new std::string[10];

std::vector<std::string>::iterator it;

std::hash<std::string> hash_fn;

size_t hash_str[str.size()];

typedef std::list<int> lint;

std::map<size_t,lint> aMap;

for (it = str.begin(), i=0; it!=str.end(); ++it, i++)
{
tmp = *it;

std::sort(tmp.begin(), tmp.end());

hash_str[i] = hash_fn(tmp);

aMap[hash_str[i]].push_back(i);
}

cout << endl;

for (std::map<size_t,lint>::iterator ait=aMap.begin(); ait !=aMap.end(); ++ait)
{
for(lint::iterator lit = (*ait).second.begin(); lit != (*ait).second.end() ;++lit)
cout << str[*lit] << "\t";

cout << endl;
}

return 0;
}

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <list>
#include <string>
using namespace std;

int main()
{
	uint32_t i;
	std::string tmp;

	std::vector<std::string> str = {"abccd", "efgh", "hytr", "yincec", "ccdba", "cdcba", "yucybd", "hgfe", "ghfe"};
	//std::string *str = new std::string[10];

	std::vector<std::string>::iterator it;

	std::hash<std::string> hash_fn;

	size_t hash_str[str.size()];

	typedef std::list<int> lint;

	std::map<size_t,lint> aMap;

	for (it = str.begin(), i=0; it!=str.end(); ++it, i++)
	{
		tmp = *it;

		std::sort(tmp.begin(), tmp.end());

		hash_str[i] = hash_fn(tmp);
		
		aMap[hash_str[i]].push_back(i);
	}
		
	cout << endl;

	for (std::map<size_t,lint>::iterator ait=aMap.begin(); ait !=aMap.end(); ++ait)
	{
		for(lint::iterator lit = (*ait).second.begin(); lit != (*ait).second.end() ;++lit)
			cout << str[*lit] << "\t";

		cout << endl;
	}

	return 0;
}

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <list>
#include <string>
using namespace std;

int main()
{
	uint32_t i;
	std::string tmp;

	std::vector<std::string> str = {"abccd", "efgh", "hytr", "yincec", "ccdba", "cdcba", "yucybd", "hgfe", "ghfe"};
	//std::string *str = new std::string[10];

	std::vector<std::string>::iterator it;

	std::hash<std::string> hash_fn;

	size_t hash_str[str.size()];

	typedef std::list<int> lint;

	std::map<size_t,lint> aMap;

	for (it = str.begin(), i=0; it!=str.end(); ++it, i++)
	{
		tmp = *it;

		std::sort(tmp.begin(), tmp.end());

		hash_str[i] = hash_fn(tmp);
		
		aMap[hash_str[i]].push_back(i);
	}
		
	cout << endl;

	for (std::map<size_t,lint>::iterator ait=aMap.begin(); ait !=aMap.end(); ++ait)
	{
		for(lint::iterator lit = (*ait).second.begin(); lit != (*ait).second.end() ;++lit)
			cout << str[*lit] << "\t";

		cout << endl;
	}

	return 0;
}

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <list>
#include <string>
using namespace std;

int main()
{
	uint32_t i;
	std::string tmp;

	typedef std::vector<std::string> vstring;
	vstring str = {"abccd", "efgh", "hytr", "yincec", "ccdba", "cdcba", "yucybd", "hgfe", "ghfe"};

	vstring::iterator it;

	std::hash<std::string> hash_fn;

	size_t hash_str[str.size()];

	typedef std::list<int> lint;
	std::map<size_t,lint> aMap;

	for (it = str.begin(), i=0; it!=str.end(); ++it, i++)
	{
		tmp = *it;

		std::sort(tmp.begin(), tmp.end() );

		hash_str[i] = hash_fn(tmp);
		
		aMap[hash_str[i]].push_back(i);
	}
	
	for (std::map<size_t,lint>::iterator ait=aMap.begin(); ait !=aMap.end(); ++ait)
	{
		for(lint::iterator lit = (*ait).second.begin(); lit != (*ait).second.end() ;++lit)
			cout << str[*lit] << "\t";

		cout << endl;
	}

	return 0;
}

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <list>
#include <string>
using namespace std;

int main()
{
uint32_t i;
std::string tmp;

typedef std::vector<std::string> vstring;
vstring str = {"abccd", "efgh", "hytr", "yincec", "ccdba", "cdcba", "yucybd", "hgfe", "ghfe"};

vstring::iterator it;

std::hash<std::string> hash_fn;

size_t hash_str[str.size()];

typedef std::list<int> lint;
std::map<size_t,lint> aMap;

for (it = str.begin(), i=0; it!=str.end(); ++it, i++)
{
tmp = *it;

std::sort(tmp.begin(), tmp.end() );

hash_str[i] = hash_fn(tmp);

aMap[hash_str[i]].push_back(i);
}

for (std::map<size_t,lint>::iterator ait=aMap.begin(); ait !=aMap.end(); ++ait)
{
for(lint::iterator lit = (*ait).second.begin(); lit != (*ait).second.end() ;++lit)
cout << str[*lit] << "\t";

cout << endl;
}

return 0;
}

import java.util.*;
public class id5639359996887040
{
	public static void main(String[] args)
	{
		ArrayList<String> myList = new ArrayList<String>();
		myList.add("abc"); myList.add("cab"); myList.add("dac");
		myList.add("beed"); myList.add("deb"); myList.add("few");
		myList.add("acd");
	
		HashSet<String> mySet = new HashSet<String>();
		for (int i = 0; i < myList.size(); i ++)
		{
		    char[] charArr = myList.get(i).toCharArray();
		    Arrays.sort(charArr);
            mySet.add(new String(charArr));
		}
		System.out.println("size: " + mySet.size());
	}

}

Since only alphabets are considered for anagrams. Find hash for each string using hash formula as ascii sum of characters in string

def anagrams(input_list):
	hash_list = {}
	for inp in input_list:
		total_val = 0
		for ch in inp:
			ascii_val = ord(ch)
			if (ascii_val > 96 and ascii_val < 122) or (ascii_val > 65 and ascii_val < 90):
				total_val += ascii_val

		hash_list[total_val] = hash_list.get(total_val, [])
		hash_list.get(total_val, []).append(inp)
	print hash_list
	print len(hash_list.keys())

>>> def anagrams(input_list):
	hash_list = {}
	for inp in input_list:
		total_val = 0
		for ch in inp:
			ascii_val = ord(ch)
			if (ascii_val > 96 and ascii_val < 122) or (ascii_val > 65 and ascii_val < 90):
				total_val += ascii_val

		hash_list[total_val] = hash_list.get(total_val, [])
		hash_list.get(total_val, []).append(inp)
	print hash_list
	print len(hash_list.keys())

import java.util.ArrayList;

class MainProg {
ArrayList<String> checkWords = new ArrayList<>();
ArrayList<Integer> numberWords = new ArrayList<>();

public static void main(String[] args) {

ArrayList<String> words = new ArrayList<>();
words.add("abc");
words.add("cab");
words.add("dac");
words.add("beed");
words.add("deb");
words.add("few");
words.add("acd");

MainProg program = new MainProg(words);
program.findasciiNumberforEachSet();
System.out.println(program.NumberofAnagrams());
}

public MainProg ( ArrayList<String> words){
checkWords = words;
}

void findasciiNumberforEachSet(){

for (int i = 0; i < checkWords.size(); i++){
numberWords.add(0);
}
for (int i = 0; i < checkWords.size(); i++){
for (int j = 0; j < checkWords.get(i).length(); j++){
int temp = (int)checkWords.get(i).charAt(j);
numberWords.set(i, numberWords.get(i)+ temp);
}
}
}

int NumberofAnagrams (){

for (int i = 0; i < numberWords.size(); i++){
for (int j= i+1 ;j < numberWords.size(); j++){
int x = numberWords.get(i);
int y = numberWords.get(j);

if (x == y){
numberWords.remove(j);
}
}
}
return numberWords.size();
}
}

1. Use Hashmap to get all the unique counts of strings .
2. Hash function :

	I) assign prime numbers to all the alphabets starting from 3
		a = 3 , b = 5, c = 7, d  = 11 .... till  z
	II) for a given string generate the sum from above sequence 
		eg. for abc = 3+5+7 = 15
		      for bca = 5+7+3 = 15
		
	III) for hash function string sum(generated above) is the output.

That looks wrong. Note that 5+11 = 3 + 13...

int result = 0;
String[] words = new String[]{"abc", "cab", "dac", "beed", "deb", "few", "acd", "silent", "listen"};
Set<String> values = new HashSet<>();
for (String word : words) {
char[] c = word.toCharArray();
Arrays.sort(c);
if (values.add(new String(c))) {
result++;
}
}
System.out.println(result);

int result = 0;
String[] words = new String[]{"abc", "cab", "dac", "beed", "deb", "few", "acd", "silent", "listen"};
Set<String> values = new HashSet<>();
        for (String word : words) {
            char[] c = word.toCharArray();
            Arrays.sort(c);
            if (values.add(new String(c))) {
                result++;
            }
        }
System.out.println(result);

int result = 0;
String[] words = new String[]{"abc", "cab", "dac", "beed", "deb", "few", "acd", "silent", "listen"};
Set<String> values = new HashSet<>();
for (String word : words) {
    char[] c = word.toCharArray();
    Arrays.sort(c);
    if (values.add(new String(c))) {
        result++;
    }
}
System.out.println(result);