Algorithm🧑🏻💻
👉🏻 Firstly, declare a hashTable that will store the index of all the words with the same key.
👉🏻Make a function createKey which will return the key for the string.
👉🏻Now run the loop for ‘i’ in the range from ‘0’ to ‘n-1’
-
Insert ‘i’ in the hashTable for the 'wordsInList[i]' key.
👉🏻 Now, traverse through the hash table and print the strings with the same key.
Implementation In C++💻
C++ code for the problem group words with same set of characters is -
#include<bits/stdc++.h>
using namespace std;
string createKey(string& word)
{
string key;
vector<bool> charSet(26,false);
for(auto ele:word)
{
charSet[ele-'a']=true;
}
for(int i=0;i<26;i++)
{
if(charSet[i])
{
key+=(char)(i+'a');
}
}
return key;
}
void wordsInListWithSameSetOfchar(vector<string>& wordsInList)
{
int n=wordsInList.size();
unordered_map<string,vector<int>> hashTable;
for(int i=0;i<n;i++)
{
hashTable[createKey(wordsInList[i])].push_back(i);
}
for(auto keys:hashTable)
{
for(auto index:keys.second)
{
cout<<wordsInList[index]<<", ";
}
cout<<endl;
}
return;
}
int main()
{
vector<string> wordsInList={ "may", "goddess", "cat", "act","tab", "student", "odist", "dossed","studio","bat","amy", "yam", "blow", "bowl", "lambs", "balms", "looped", "poodle"};
wordsInListWithSameSetOfchar(wordsInList);
return 0;
}
You can also try this code with Online C++ Compiler
Output -
blow, bowl,
lambs, balms,
studio,
odist,
student,
looped, poodle,
tab, bat,
cat, act,
dossed,
goddess,
may, amy, yam,
Implementation In Java💻
Java code for the problem group words with same set of characters is -
import java.util.*;
import java.util.Map.Entry;
public class Main
{
static String createKey(String wordInList)
{
boolean[] charSet = new boolean[26];
for(int l=0;l<wordInList.length();l++)
{
charSet[wordInList.charAt(l)-'a']=true;
}
String key="";
for(int i=0;i<26;i++)
{
if(charSet[i])
{
key+=(char)(i+'a');
}
}
return key;
}
static void wordsInListWithSameSetOfchar(String wordsInList[])
{
int n=wordsInList.length;
HashMap<String, ArrayList<Integer>> hashTable = new HashMap<>();
for (int i=0; i<n; i++)
{
String key = createKey(wordsInList[i]);
if(hashTable.containsKey(key))
{
ArrayList<Integer> temp = hashTable.get(key);
temp.add(i);
hashTable.put(key, temp);
}
else
{
ArrayList<Integer> temp = new ArrayList<>();
temp.add(i);
hashTable.put(key, temp);
}
}
for (Entry<String, ArrayList<Integer>> keys : hashTable.entrySet())
{
ArrayList<Integer> indices =keys.getValue();
for (Integer index:indices)
System.out.print( wordsInList[index] + ", ");
System.out.println();
}
return;
}
public static void main(String[] args) {
String wordsInList[]={ "may", "goddess", "cat", "act","tab", "student", "odist", "dossed","studio","bat","amy", "yam", "blow", "bowl", "lambs", "balms", "looped", "poodle"};
wordsInListWithSameSetOfchar(wordsInList);
}
}
You can also try this code with Online Java Compiler
Output -
student,
tab, bat,
cat, act,
lambs, balms,
odist,
goddess,
studio,
dossed,
may, amy, yam,
blow, bowl,
looped, poodle,
Implementation In Python💻
Python code for the problem group words with same set of characters is -
from collections import Counter
def groupStrings(input):
dict={}
for wordInList in input:
wordDict=Counter(wordInList)
key = wordDict.keys()
key = sorted(key)
key = ''.join(key)
if key in dict.keys():
dict[key].append(wordInList)
else:
dict[key]=[]
dict[key].append(wordInList)
for (key,value) in dict.items():
print (','.join(dict[key]))
if __name__ == "__main__":
input=["may", "goddess", "cat", "act","tab", "student", "odist", "dossed","studio","bat","amy", "yam", "blow", "bowl", "lambs", "balms", "looped", "poodle"]
groupStrings(input)
You can also try this code with Online Python Compiler
Output -
may,amy,yam
goddess
cat,act
tab,bat
student
odist
dossed
studio
blow,bowl
lambs,balms
looped,poodle
You can also read about the Longest Consecutive Sequence.
Complexities🎯
The time and space complexity of the given solution for the problem statement to group words with same set of characters are given below.
Time Complexity
We traverse the array only once, and in each iteration, we create a key by iterating over the given string. If the string length is taken as "L" and “N” is the number of words in the dictionary, the time complexity of the above-given solution is O(N*L).
Space Complexity
O(N) space is needed to store the hash table in the above solution where “N” is the number of words in the dictionary.
Frequently Asked Questions🤔
What is hashing?
In the data structure, hashing is a technique of mapping a large part of data into small tables using a hashing function.
What is a list?
A type of ordered data structure is called a list. Elements are separated by commas in the list and enclosed within the square brackets.
What are anagrams?
It is a phrase or a word that is made by arranging the letters of any other phrase or word in a different order.
What is the anagram of the word "Sing"?
The anagram of the word sing can be the words like sign, gins, etc.
What is Boolean?
A data type called boolean has two possible values to assign, which are also called truth values that are "true" and "false".
Conclusion
In this blog, we discussed the problem statement to group words with same set of characters using hashing method, including the Algorithm, code, and its complexities if you would like to learn more, check out our articles on Count quadruples from four sorted arrays whose sum is equal to a given value x and Count Divisible Pairs in an Array.
Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.
Do upvote our blog to help other ninjas grow.
Happy Learning Ninja! 🥷
38+ registered 
