Group words with same set of characters

Last Updated : 16 Jan, 2023

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 : 
looped, poodle, 
lambs, balms, 
flow, wolf, 
tab, bat, 
may, amy, yam, 
student, students, studentssess, 
dog, god, 
cat, act, 

All words with same set of characters are printed 
together in a line.

The idea is to use hashing. We generate a key for all words. The key contains all unique characters (The size of the key is at most 26 for lowercase alphabets). We store indexes of words as values for a key. Once we have filled all keys and values in the hash table, we can print the result by traversing the table.

Below is the implementation of the above idea.

C++

// C++ program to print all words that have
// the same unique character set
#include<bits/stdc++.h>
using namespace std;
#define MAX_CHAR 26
 
// Generates a key from given string. The key
// contains all unique characters of given string in
// sorted order consisting of only distinct elements.
string getKey(string &str)
{
    bool visited[MAX_CHAR] = { false };
 
    // store all unique characters of current
    // word in key
    for (int j = 0; j < str.length(); j++)
        visited[str[j] - 'a'] = true ;
    string key = "";
    for (int j=0; j < MAX_CHAR; j++)
        if (visited[j])
            key = key + (char)('a'+j);
    return key;
}
 
// Print all words together with same character sets.
void wordsWithSameCharSet(string words[], int n)
{
    // Stores indexes of all words that have same
    // set of unique characters.
    unordered_map <string, vector <int> > Hash;
 
    // Traverse all words
    for (int i=0; i<n; i++)
    {
        string key = getKey(words[i]);
        Hash[key].push_back(i);
    }
 
    // print all words that have the same unique character set
    for (auto it = Hash.begin(); it!=Hash.end(); it++)
    {
      for (auto v=(*it).second.begin(); v!=(*it).second.end(); v++)
          cout << words[*v] << ", ";
      cout << endl;
    }
}
 
// Driver program to test above function
int main()
{
    string words[] = { "may", "student", "students", "dog",
                 "studentssess", "god", "cat", "act", "tab",
                 "bat", "flow", "wolf", "lambs", "amy", "yam",
                 "balms", "looped", "poodle"};
    int n = sizeof(words)/sizeof(words[0]);
    wordsWithSameCharSet(words, n);
    return 0;
}

Java

// Java program to print all words that have
// the same unique character set
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map.Entry;
public class GFG {
  
    static final int MAX_CHAR = 26;
      
    // Generates a key from given string. The key
    // contains all unique characters of given string
    // in sorted order consisting of only distinct elements.
    static String getKey(String str)
    {
        boolean[] visited = new boolean[MAX_CHAR];
        Arrays.fill(visited, false);
      
        // store all unique characters of current
        // word in key
        for (int j = 0; j < str.length(); j++)
            visited[str.charAt(j) - 'a'] = true ;
        String key = "";
        for (int j=0; j < MAX_CHAR; j++)
            if (visited[j])
                key = key + (char)('a'+j);
        return key;
    }
      
    // Print all words together with same character sets.
    static void wordsWithSameCharSet(String words[], int n)
    {
        // Stores indexes of all words that have same
        // set of unique characters.
        //unordered_map <string, vector <int> > Hash;
        HashMap<String, ArrayList<Integer>> Hash = new HashMap<>();
      
        // Traverse all words
        for (int i=0; i<n; i++)
        {
            String key = getKey(words[i]);
             
            // if the key is already in the map
            // then get its corresponding value
            // and update the list and put it in the map
            if(Hash.containsKey(key))
            {
                ArrayList<Integer> get_al = Hash.get(key);
                get_al.add(i);
                Hash.put(key, get_al);
            }
             
            // if key is not present in the map
            // then create a new list and add
            // both key and the list
            else
            {
                ArrayList<Integer> new_al = new ArrayList<>();
                new_al.add(i);
                Hash.put(key, new_al);
            }
        }
      
        // print all words that have the same unique character set
        for (Entry<String, ArrayList<Integer>> it : Hash.entrySet())
        {
            ArrayList<Integer> get =it.getValue();
            for (Integer v:get)
                System.out.print( words[v] + ", ");
            System.out.println();
        }
    }
      
    // Driver program to test above function
    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"};
        int n = words.length;
        wordsWithSameCharSet(words, n);
    }
}
// This code is contributed by Sumit Ghosh

Python3

# Python program to print all words that
# have the same unique character set
 
# Function to group all strings with same characters
from collections import Counter
 
def groupStrings(input):
    # traverse all strings one by one
    # dict is an empty dictionary
    dict={}
     
    for word in input:
        # sort the current string and take it's
        # sorted value as key
        # sorted return list of sorted characters
        # we need to join them to get key as string
        # Counter() method returns dictionary with frequency of
        # each character as value
        wordDict=Counter(word)
 
        # now get list of keys
        key = wordDict.keys()
 
        # now sort these keys
        key = sorted(key)
 
        # join these characters to produce key string
        key = ''.join(key)
         
        # now check if this key already exist in
        # dictionary or not
        # if exist then simply append current word
        # in mapped list on key
        # otherwise first assign empty list to key and
        # then append current word in it
        if key in dict.keys():
            dict[key].append(word)
        else:
            dict[key]=[]
            dict[key].append(word)
 
        # now traverse complete dictionary and print
        # list of mapped strings in each key separated by ,
    for (key,value) in dict.items():
        print (','.join(dict[key]))
         
# Driver program
if __name__ == "__main__":
    input=['may','student','students','dog','studentssess','god','cat','act','tab','bat','flow','wolf','lambs','amy','yam','balms','looped','poodle']
    groupStrings(input)

C#

// C# program to print all words that
// have the same unique character set
using System;
using System.Collections.Generic;
 
class GFG{
  
static readonly int MAX_CHAR = 26;
  
// Generates a key from given string. The
// key contains all unique characters of
// given string in sorted order consisting
// of only distinct elements.
static String getKey(String str)
{
    bool[] visited = new bool[MAX_CHAR];
  
    // Store all unique characters of current
    // word in key
    for(int j = 0; j < str.Length; j++)
        visited[str[j] - 'a'] = true;
         
    String key = "";
     
    for(int j = 0; j < MAX_CHAR; j++)
        if (visited[j])
            key = key + (char)('a' + j);
             
    return key;
}
  
// Print all words together with same character sets.
static void wordsWithSameCharSet(String []words, int n)
{
     
    // Stores indexes of all words that have same
    // set of unique characters.
    //unordered_map <string, vector <int> > Hash;
    Dictionary<String, 
               List<int>> Hash = new Dictionary<String, 
                                                List<int>>();
  
    // Traverse all words
    for (int i = 0; i < n; i++)
    {
        String key = getKey(words[i]);
         
        // If the key is already in the map
        // then get its corresponding value
        // and update the list and put it
        // in the map
        if (Hash.ContainsKey(key))
        {
            List<int> get_al = Hash[key];
            get_al.Add(i);
            Hash[key]= get_al;
        }
         
        // If key is not present in the map
        // then create a new list and add
        // both key and the list
        else
        {
            List<int> new_al = new List<int>();
            new_al.Add(i);
            Hash.Add(key, new_al);
        }
    }
  
    // Print all words that have the 
    // same unique character set
    foreach(KeyValuePair<String, List<int>> it in Hash)
    {
        List<int> get =it.Value;
        foreach(int v in get)
            Console.Write( words[v] + ", ");
             
        Console.WriteLine();
    }
}
  
// Driver code
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"};
                        
    int n = words.Length;
     
    wordsWithSameCharSet(words, n);
}
}
 
// This code is contributed by Princi Singh

Javascript

<script>
 
const MAX_CHAR = 26;
 
// Generates a key from given string. The key
// contains all unique characters of given string in
// sorted order consisting of only distinct elements.
function getKey(str) {
  let visited = new Array(MAX_CHAR).fill(false);
 
  // store all unique characters of current
  // word in key
  for (let j = 0; j < str.length; j++) {
    visited[str.charCodeAt(j) - 97] = true;
  }
  let key = "";
  for (let j = 0; j < MAX_CHAR; j++) {
    if (visited[j]) {
      key += String.fromCharCode(97 + j);
    }
  }
  return key;
}
 
// Print all words together with same character sets.
function wordsWithSameCharSet(words, n) {
  // Stores indexes of all words that have same
  // set of unique characters.
  let Hash = {};
 
  // Traverse all words
  for (let i = 0; i < n; i++) {
    let key = getKey(words[i]);
    if (key in Hash) {
      Hash[key].push(i);
    } else {
      Hash[key] = [i];
    }
  }
 
  // print all words that have the same unique character set
  for (let key in Hash) {
    for (let v of Hash[key]) {
      console.log(words[v] + ", ");
    }
    console.log("\n");
  }
}
 
// Driver program to test above function
function main() {
  let words = [    "may",    "student",    "students",    "dog",    "studentssess",    "god",    "cat",    "act",    "tab",    "bat",    "flow",    "wolf",    "lambs",    "amy",    "yam",    "balms",    "looped",    "poodle",  ];
  let n = words.length;
  wordsWithSameCharSet(words, n);
}
 
main();
 
 
</script>

Output

looped, poodle, 
student, students, studentssess, 
may, amy, yam, 
dog, god, 
cat, act, 
tab, bat, 
lambs, balms, 
flow, wolf,

Time Complexity: O(n*k) where n is number of words in dictionary and k is maximum length of a word.
Auxiliary Space: O(n*k), where n is number of words in dictionary and k is maximum length of a word.

N

Nishant Singh

Improve

Previous Article

Find all pairs (a, b) in an array such that a % b = k

k-th distinct (or non-repeating) element among unique elements in an array.

Similar Reads

Check If every group of a's is followed by a group of b's of same length

Given string str, the task is to check whether every group of consecutive a's is followed by a group of consecutive b's of the same length. If the condition is true for every group then print 1 else print 0. Examples: Input: str = "ababaabb" Output: 1 ab, ab, aabb. All groups are valid Input: str = "aabbabb" Output: 0 aabb, abb (A single 'a' follow

Minimize group such that no two range of same group intersect

Given an array ranges[] of size N (1 ? N ? 105), where ranges[i] = {starti, endi} represents the range between starti to endi (both inclusive). The task is to find the minimum number of groups that are needed such that each interval of ranges[] belongs to exactly one group and no two ranges[i] in the same group will intersect with each other. Note:

Python | Toggle characters in words having same case

Given a string, toggle the characters of those words who have all their characters in the same case. Examples: Input : Geeks for Geeks Output : Geeks FOR Geeks Explanation: The string contains three words "Geeks", "for", "Geeks" out of which the word "for" contains all its characters as lower cases, therefore, toggle the case of the word. Print the

Group consecutive characters of same type in a string

Given a string str consisting of upper case alphabets, numeric digits and arithmetic operators, the task is to group them into continuous sub-strings of the same type.Examples: Input: str = "G E E K S 1 2 3 4 5" Output: GEEKS 12345 All contiguous upper case characters can be grouped together and all the numeric characters can be grouped together in

Maximize cost of forming a set of words using given set of characters

Given an array arr[] consisting of N strings, an array letter[] consisting of M lowercase characters, and an array score[] such that score[i] is the cost of ith English alphabets, the task is to find the maximum cost of any valid set of words formed by using the given letters such that each letter can be used at most once and each word arr[i] can b

Check whether two strings contain same characters in same order

Given two strings s1 and s2, the task is to find whether the two strings contain the same characters that occur in the same order. For example string "Geeks" and string "Geks" contain the same characters in same order. Examples: Input: s1 = "Geeks", s2 = "Geks" Output: Yes Input: s1 = "Arnab", s2 = "Andrew" Output: No Approach: We have two strings

Check if given strings can be made same by swapping two characters of same or different strings

Given an array of equal-length strings, arr[] of size N, the task is to check if all the strings can be made equal by repeatedly swapping any pair of characters of same or different strings from the given array. If found to be true, then print "YES". Otherwise, print "NO". Examples: Input: arr[] = { "acbdd", "abcee" } Output: YES Explanation: Swapp

Minimum characters that are to be inserted such that no three consecutive characters are same

Given a string str and the task is to modify the string such that no three consecutive characters are the same. In a single operation, any character can be inserted at any position in the string. Find the minimum number of such operations required. Examples: Input : str = "aabbbcc" Output: 1 Explanation: "aabbdbcc" is the modified string. Input: st

Minimum characters to be replaced to make frequency of all characters same

Given a string S consisting of alphabets ['A' - 'Z'], the task is to find the minimum number of operations required to make frequency of every character equal. In one operation any character of the string can be chosen and replaced with another valid character.Examples: Input: S = "ABCB" Output: 1 Explanation: In the given string character 'C' can

Modify characters of a string by adding integer values of same-indexed characters from another given string

Given two strings S and N of the same length, consisting of alphabetical and numeric characters respectively, the task is to generate a new string obtained by adding the integer value of each character of string N with the ASCII value of the same indexed character of string S. Finally, print the resultant string.Note: If the sum exceeds 122, then s

Article Tags :

Practice Tags :