Given an array of strings arr[] consisting of N strings, the task is to categorize the strings according to the hash value obtained by adding ASCII values % 26 of the characters in the string.
Examples:
Input: arr[][] = {“neveropen”, “for”, “neveropen”}
Output:
neveropen neveropen
for
Explanation:
The hash value of string “for” is (102 + 111 + 114) % 26 = 14
The hash value of string “neveropen” is (103 + 101 + 101 + 107 + 115) % 26 = 7
Therefore, two “neveropen” are grouped together and “for” is kept in another group.Input: arr[][] = {“adf”, “aahe”, “bce”, “bgdb”}
Output:
aahe bgdb
bce
adf
Explanation:
The hash value of string “adf” is (97 + 100 + 102)%26 = 13
The hash value of string “aahe” is (97 + 97 + 104 + 101)%26 = 9
The hash value of string “bce” is (98 + 99 + 101)%26 = 12
The hash value of string “bgdb” is (98 + 103 + 100 + 98)%26 = 9
Therefore, strings “aahe” and “bgdb” have same hashed value, so they are grouped together.
Approach: The idea is to use Map Data Structure for grouping together the strings with the same hash values. Follow the steps below to solve the problem:
- Initialize a Map, say mp, to map hash values with respective strings in a vector.
- Traverse the given array of strings and perform the following steps:
- Calculate the hash value of the current string according to the given function.
- Push the string into the vector with the calculated hash values of the string as key in the map mp.
- Finally, traverse the map mp and print all the strings of respective keys.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the hash// value of the string sint stringPower(string s){ // Stores hash value of string int power = 0; int n = s.length(); // Iterate over characters of the string for (int i = 0; i < n; i++) { // Calculate hash value power = (power + (s[i])) % 26; } // Return the hash value return power;}// Function to classify the strings// according to the given conditionvoid categorisation_Of_strings( vector<string> s, int N){ // Maps strings with their strings // respective hash values map<int, vector<string> > mp; // Traverse the array of strings for (int i = 0; i < N; i++) { // Find the hash value of the // of the current string int temp = stringPower(s[i]); // Push the current string in // value vector of temp key mp[temp].push_back(s[i]); } // Traverse over the map mp for (auto power : mp) { // Print the result for (auto str : power.second) { cout << str << " "; } cout << endl; }}// Driver Codeint main(){ vector<string> arr{ "adf", "aahe", "bce", "bgdb" }; int N = arr.size(); categorisation_Of_strings(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.Arrays;import java.util.HashMap;import java.util.Map;import java.util.Vector;class GFG{ // Function to find the hash// value of the string sstatic int stringPower(String s){ // Stores hash value of string int power = 0; int n = s.length(); char C[] = s.toCharArray(); // Iterate over characters of the string for(int i = 0; i < n; i++) { // Calculate hash value power = (power + (C[i])) % 26; } // Return the hash value return power;}// Function to classify the strings// according to the given conditionstatic void categorisation_Of_strings(Vector<String> s, int N){ // Maps strings with their strings // respective hash values Map<Integer, Vector<String> > mp = new HashMap<>(); // Traverse the array of strings for(int i = 0; i < N; i++) { // Find the hash value of the // of the current string int temp = stringPower(s.get(i)); // Push the current string in // value vector of temp key if (mp.containsKey(temp)) { mp.get(temp).add(s.get(i)); } else { mp.put(temp, new Vector<String>()); mp.get(temp).add(s.get(i)); } } // Traverse over the map mp for(Map.Entry<Integer, Vector<String>> entry : mp.entrySet()) { // Print the result for(String str : entry.getValue()) { System.out.print(str + " "); } System.out.println(); }}// Driver codepublic static void main(String[] args){ String[] Sarr = { "adf", "aahe", "bce", "bgdb" }; Vector<String> arr = new Vector<String>( Arrays.asList(Sarr)); int N = arr.size(); categorisation_Of_strings(arr, N);}}// This code is contributed by abhinavjain194 |
Python3
# Python3 program for the above approach# Function to find the hash# value of the string sdef stringPower(s): # Stores hash value of string power = 0 n = len(s) # Iterate over characters of the string for i in range(n): # Calculate hash value power = (power + ord(s[i])) % 26 # Return the hash value return power# Function to classify the strings# according to the given conditiondef categorisation_Of_strings(s, N): # Maps strings with their strings # respective hash values mp = {} # Traverse the array of strings for i in range(N): # Find the hash value of the # of the current string temp = stringPower(s[i]) # Push the current string in # value vector of temp key if temp in mp: mp[temp].append(s[i]) else: mp[temp] = [] mp[temp].append(s[i]) # Traverse over the map mp for i in sorted (mp) : # Print the result for str in mp[i]: print(str,end = " ") print("\n",end = "")# Driver Codeif __name__ == '__main__': arr = ["adf", "aahe", "bce", "bgdb"] N = len(arr) categorisation_Of_strings(arr, N) # This code is contributed by ipg2016107. |
Javascript
<script>// Javascript program for the above approach// Function to find the hash// value of the string sfunction stringPower(s){ // Stores hash value of string var power = 0; var n = s.length; // Iterate over characters of the string for(var i = 0; i < n; i++) { // Calculate hash value power = (power + (s[i].charCodeAt(0))) % 26; } // Return the hash value return power;}// Function to classify the strings// according to the given conditionfunction categorisation_Of_strings(s, N){ // Maps strings with their strings // respective hash values var mp = new Map(); // Traverse the array of strings for(var i = 0; i < N; i++) { // Find the hash value of the // of the current string var temp = stringPower(s[i]); // Push the current string in // value vector of temp key if (!mp.has(temp)) { mp.set(temp, new Array()); } var tmp = mp.get(temp); tmp.push(s[i]); mp.set(temp, tmp); } var tmp = Array(); // Traverse over the map mp mp.forEach((value, key) => { tmp.push(key); }); tmp.sort((a, b) => a - b); // Traverse over the map mp tmp.forEach((value) => { // Print the result mp.get(value).forEach(element => { document.write(element + " "); }); document.write("<br>"); });}// Driver Codevar arr = [ "adf", "aahe", "bce", "bgdb" ];var N = arr.length;categorisation_Of_strings(arr, N);// This code is contributed by rutvik_56</script> |
C#
using System;using System.Collections.Generic;using System.Linq;namespace ConsoleApp1{ class Program { // Function to find the hash // value of the string s static int StringPower(string s) { // Stores hash value of string int power = 0; int n = s.Length; char[] C = s.ToCharArray(); // Iterate over characters of the string for (int i = 0; i < n; i++) { // Calculate hash value power = (power + (C[i])) % 26; } // Return the hash value return power; } // Function to classify the strings // according to the given condition static void CategorisationOfStrings(List<string> s, int N) { // Maps strings with their strings // respective hash values SortedDictionary<int, List<string>> mp = new SortedDictionary<int, List<string>>(); // Traverse the array of strings for (int i = 0; i < N; i++) { // Find the hash value of the // of the current string int temp = StringPower(s[i]); // Push the current string in // value vector of temp key if (mp.ContainsKey(temp)) { mp[temp].Add(s[i]); } else { mp[temp] = new List<string>(); mp[temp].Add(s[i]); } } // Traverse over the map mp foreach (var entry in mp) { // Print the result foreach (string str in entry.Value) { Console.Write(str + " "); } Console.WriteLine(); } } static void Main(string[] args) { string[] Sarr = { "adf", "aahe", "bce", "bgdb" }; List<string> arr = new List<string>(Sarr); int N = arr.Count; CategorisationOfStrings(arr, N); } }} |
Output
aahe bgdb bce adf
Time Complexity: O(N*M), where M is the length of the longest string.
Auxiliary Space: O(N*M)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
