# Group Words With Same Set of Characters

Difficulty Level Medium
Frequently asked in BlackRock Citrix IBM JP Morgan SAP Labs Xome
Hash String

In Group words with same set of characters problem, we have given a list of words with lower cases. Implement a function to find all Words that have the same unique character set.

## Example

Input

Words[]={ “may”, “student”, “students”, “dog”,”studentssess”, “god”, “cat”, “act”,”tab”, “bat”, “flow”, “wolf”, “lambs”,”amy”, “yam”, “balms”, “looped”, “poodle”}

Output

may, amy, yam,

student, students, studentssess,

dog, god,

cat, act,

tab, bat,

flow, wolf,

lambs, balms,

looped, poodle

## Approach 1: Brute force

### Main idea

For each word, we will iterate over all the words and find those words with the same set of characters and then print it.

The words we have already printed, we will mark them so that we will not print them again.

### Algorithm for Group Words With Same Set of Characters

1. Run a loop for I in range 0 to n-1
1. If the length of the words[i] is equal, then skip it because we have already printed it.
2. Make an array charSet1 which will store the characters which are present in words[i].
3. Run a loop for j in the range I to n-1
1. Make an array charSet2 which will store the characters which are present in words[j]
2. If charSet1 is equal to charSet2, then print words[j] and change words[j] to an empty string which denotes that we have printed this string.
4. Return
Longest Repeated Subsequence

### Implementation for Group Words With Same Set of Characters

#### C++ program

```#include<bits/stdc++.h>
using namespace std;
void wordsWithSameSetOfchar(vector<string>& words)
{
int n=words.size();
for(int i=0;i<n;i++)
{
if(words[i].length()==0)
{
continue;
}
vector<bool> charSet1(26,false);
for(auto ele:words[i])
{
charSet1[ele-'a']=true;
}
for(int j=i;j<n;j++)
{
vector<bool> charSet2(26,false);
for(auto ele:words[j])
{
charSet2[ele-'a']=true;
}
if(charSet2==charSet1)
{
cout<<words[j]<<", ";
words[j]="";
}
}
cout<<endl;
}
return;
}
int main()
{
vector<string> words={ "may", "student", "students", "dog","studentssess", "god", "cat", "act","tab", "bat", "flow", "wolf", "lambs","amy", "yam", "balms", "looped", "poodle"};
wordsWithSameSetOfchar(words);
return 0;
}
```
```may, amy, yam,
student, students, studentssess,
dog, god,
cat, act,
tab, bat,
flow, wolf,
lambs, balms,
looped, poodle,
```

#### JAVA program

```import java.util.*;
public class Main
{
static void wordsWithSameSetOfchar(String words[])
{
int n=words.length;
for(int i=0;i<n;i++)
{
if(words[i].length()==0)
{
continue;
}
boolean[] charSet1 = new boolean[26];
for(int l=0;l<words[i].length();l++)
{
charSet1[words[i].charAt(l)-'a']=true;
}
for(int j=i;j<n;j++)
{
boolean[] charSet2 = new boolean[26];
for(int l=0;l<words[j].length();l++)
{
charSet2[words[j].charAt(l)-'a']=true;
}
if(Arrays.equals(charSet2,charSet1))
{
System.out.print(words[j]+", ");
words[j]="";
}
}
System.out.println();
}
return;
}
public static void main(String[] args) {
String words[]={ "may", "student", "students", "dog","studentssess", "god", "cat", "act","tab", "bat", "flow", "wolf", "lambs","amy", "yam", "balms", "looped", "poodle"};
wordsWithSameSetOfchar(words);
}
}
```
```may, amy, yam,
student, students, studentssess,
dog, god,
cat, act,
tab, bat,
flow, wolf,
lambs, balms,
looped, poodle,
```

### Complexity Analysis

#### Time complexity

We are using three nested loops, two of them have size N, and the third one has a size of the length of strings. If we take lengths of string to be L, then the total time complexity is O(N*N*L).

#### Space complexity

We are not using any extra space so the space complexity is O(1).

## Approach 2: Using Hashing

### Main idea

We will make a key for every string which will store all the distinct characters of the string in a sorted manner. After that, we will use hashing to all the words with the same key and will print them in the end.

Second Most Repeated Word in a Sequence

### Algorithm for Group Words With Same Set of Characters

1. Declare a hash_table which will store all index of all the words having the same key.
2. Make a function makeKey, which will return the key for a string.
3. Run a loop for I in range 0 to n-1
1. Insert I in the hash_table for the key of ‘words[i]’.
4. Iterate over the hash table and print the strings with the same key.
5. Return

### Understand with example

Words = { “may”, “student”, “students”, “dog”,”studentssess”, “god”, “cat”, “act”,”tab”, “bat”, “flow”, “wolf”, “lambs”,”amy”, “yam”, “balms”, “looped”, “poodle”}

The hash table will look like this:

### Implementation for Group Words With Same Set of Characters

#### C++ program

```#include<bits/stdc++.h>
using namespace std;
string makeKey(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 wordsWithSameSetOfchar(vector<string>& words)
{
int n=words.size();
unordered_map<string,vector<int>> hash_table;
for(int i=0;i<n;i++)
{
hash_table[makeKey(words[i])].push_back(i);
}
for(auto keys:hash_table)
{
for(auto index:keys.second)
{
cout<<words[index]<<", ";
}
cout<<endl;
}
return;
}
int main()
{
vector<string> words={ "may", "student", "students", "dog","studentssess", "god", "cat", "act","tab", "bat", "flow", "wolf", "lambs","amy", "yam", "balms", "looped", "poodle"};
wordsWithSameSetOfchar(words);
return 0;
}
```
```looped, poodle,
student, students, studentssess,
may, amy, yam,
dog, god,
cat, act,
tab, bat,
lambs, balms,
flow, wolf,
```

#### JAVA program

```import java.util.*;
import java.util.Map.Entry;
public class Main
{
static String makekey(String word)
{
boolean[] charSet = new boolean[26];
for(int l=0;l<word.length();l++)
{
charSet[word.charAt(l)-'a']=true;
}
String key="";
for(int i=0;i<26;i++)
{
if(charSet[i])
{
key+=(char)(i+'a');
}
}
return key;
}
static void wordsWithSameSetOfchar(String words[])
{
int n=words.length;
HashMap<String, ArrayList<Integer>> hash_table = new HashMap<>();
for (int i=0; i<n; i++)
{
String key = makekey(words[i]);
if(hash_table.containsKey(key))
{
ArrayList<Integer> temp = hash_table.get(key);
hash_table.put(key, temp);
}
else
{
ArrayList<Integer> temp = new ArrayList<>();
hash_table.put(key, temp);
}
}
for (Entry<String, ArrayList<Integer>> keys : hash_table.entrySet())
{
ArrayList<Integer> indices =keys.getValue();
for (Integer index:indices)
System.out.print( words[index] + ", ");
System.out.println();
}
return;
}
public static void main(String[] args) {
String words[]={ "may", "student", "students", "dog","studentssess", "god", "cat", "act","tab", "bat", "flow", "wolf", "lambs","amy", "yam", "balms", "looped", "poodle"};
wordsWithSameSetOfchar(words);
}
}
```
```student, students, studentssess,
tab, bat,
cat, act,
lambs, balms,
may, amy, yam,
looped, poodle,
dog, god,
flow, wolf,
```

### Complexity Analysis

#### Time complexity

We are iterating over the array only once and in each iteration, we are generating a key by iterating over the string. So, if we take the length of the string be L, then the total time complexity is O(N*L).