Given two arrays arr1[] and arr2[] consisting of strings, the task is to print the count of anagrams of every string in arr2[] that are present in arr1[].
Examples:
Input: arr1[] = [“neveropen”, “learn”, “for”, “egeks”, “ealrn”], arr2[] = [“kgees”, “rof”, “nrael”]
Output: 2 1 2
Explanation:
Anagrams of arr2[0] (“kgees”) in arr1 : “neveropen” and “egeks”.
Anagrams of arr2[1] (“rof”) in arr1 : “for”.
Anagrams of arr2[2] (“nrael”) in arr1 : “learn” and “ealrn”.Input: arr1[] = [“code”, “to”, “grow”, “odce”], arr2[] = [“edoc”, “wgor”, “ot”]
Output: 2 1 1
Explanation:
Anagrams of arr2[0] (“edoc”) in arr1 “code” and “odce”.
Anagrams of arr2[1] (“wgor”) in arr1 “grow”.
Anagrams of arr2[2] (“ot”) in arr1 “to”
Approach:
To solve the problem, the idea is to use frequency-counting with the help of HashMap. Store the frequencies of every string in arr1[] in hashmap in their sorted form. Traverse arr2[], sort strings in arr2[], and print their respective frequencies in HashMap.
Below is the implementation of the above approach:
C++
// C++ Program to count the// number of anagrams of// each string in a given// array present in// another array#include <bits/stdc++.h>using namespace std;// Function to return the// count of anagramsvoid count(string arr1[], string arr2[], int n, int m){ // Store the frequencies // of strings in arr1[] unordered_map<string, int> freq; for (int i = 0; i < n; i++) { // Sort the string sort(arr1[i].begin(), arr1[i].end()); // Increase its frequency // in the map freq[arr1[i]]++; } for (int i = 0; i < m; i++) { // Sort the string sort(arr2[i].begin(), arr2[i].end()); // Display its anagrams // in arr1[] cout << freq[arr2[i]] << " "; }}// Driver Codeint main(){ string arr1[] = { "neveropen", "learn", "for", "egeks", "ealrn" }; int n = sizeof(arr1) / sizeof(string); string arr2[] = { "kgees", "rof", "nrael" }; int m = sizeof(arr2) / sizeof(string); count(arr1, arr2, n, m);} |
Java
// Java program to count the number // of anagrams of each String in a// given array present in// another arrayimport java.util.*;class GFG{static String sortString(String inputString) { // Convert input string to char array char tempArray[] = inputString.toCharArray(); // Sort tempArray Arrays.sort(tempArray); // Return new sorted string return new String(tempArray); } // Function to return the// count of anagramsstatic void count(String arr1[], String arr2[], int n, int m){ // Store the frequencies // of Strings in arr1[] HashMap<String, Integer> freq = new HashMap<>(); for(int i = 0; i < n; i++) { // Sort the String arr1[i] = sortString(arr1[i]); // Increase its frequency // in the map if (freq.containsKey(arr1[i])) { freq.put(arr1[i], freq.get(arr1[i]) + 1); } else { freq.put(arr1[i], 1); } } for(int i = 0; i < m; i++) { // Sort the String arr2[i] = sortString(arr2[i]); // Display its anagrams // in arr1[] System.out.print(freq.get(arr2[i]) + " "); }}// Driver Codepublic static void main(String[] args){ String arr1[] = { "neveropen", "learn", "for", "egeks", "ealrn" }; int n = arr1.length; String arr2[] = { "kgees", "rof", "nrael" }; int m = arr2.length; count(arr1, arr2, n, m);}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program to count the number# of anagrams of each string in a # given array present in another array # Function to return the count of anagramsdef count(arr1, arr2, n, m): # Store the frequencies of # strings in arr1 freq = {} for word in arr1: # Sort the string word = ' '.join(sorted(word)) # Increase its frequency if word in freq.keys(): freq[word] = freq[word] + 1 else: freq[word] = 1 for word in arr2: # Sort the string word = ' '.join(sorted(word)) # Display its anagrams # in arr1 if word in freq.keys(): print(freq[word], end = " ") else: print(0, end = " ") print() # Driver Codeif __name__ == '__main__': arr1 = [ "neveropen", "learn", "for", "egeks", "ealrn" ] n = len(arr1) arr2 = [ "kgees", "rof", "nrael" ] m = len(arr2) count(arr1, arr2, n, m)# This code is contributed by Pawan_29 |
C#
// C# program to count the number // of anagrams of each String in a// given array present in// another arrayusing System;using System.Collections.Generic;class GFG{static String sortString(String inputString) { // Convert input string to char array char []tempArray = inputString.ToCharArray(); // Sort tempArray Array.Sort(tempArray); // Return new sorted string return new String(tempArray); } // Function to return the// count of anagramsstatic void count(String []arr1, String []arr2, int n, int m){ // Store the frequencies // of Strings in arr1[] Dictionary<String, int> freq = new Dictionary<String, int>(); for(int i = 0; i < n; i++) { // Sort the String arr1[i] = sortString(arr1[i]); // Increase its frequency // in the map if (freq.ContainsKey(arr1[i])) { freq[arr1[i]] = freq[arr1[i]] + 1; } else { freq.Add(arr1[i], 1); } } for(int i = 0; i < m; i++) { // Sort the String arr2[i] = sortString(arr2[i]); // Display its anagrams // in arr1[] Console.Write(freq[arr2[i]] + " "); }}// Driver Codepublic static void Main(String[] args){ String []arr1 = { "neveropen", "learn", "for", "egeks", "ealrn" }; int n = arr1.Length; String []arr2 = { "kgees", "rof", "nrael" }; int m = arr2.Length; count(arr1, arr2, n, m);}}// This code is contributed by Amit Katiyar |
Javascript
<script>// Javascript program to count the number// of anagrams of each String in a// given array present in// another arrayfunction sortString(inputString){ // Convert input string to char array let tempArray = inputString.split(''); // Sort tempArray tempArray.sort(); // Return new sorted string return tempArray.join("");} // Function to return the// count of anagramsfunction count(arr1, arr2, n, m){ // Store the frequencies // of Strings in arr1[] let freq = new Map(); for(let i = 0; i < n; i++) { // Sort the String arr1[i] = sortString(arr1[i]); // Increase its frequency // in the map if (freq.has(arr1[i])) { freq.set(arr1[i], freq.get(arr1[i]) + 1); } else { freq.set(arr1[i], 1); } } for(let i = 0; i < m; i++) { // Sort the String arr2[i] = sortString(arr2[i]); // Display its anagrams // in arr1[] document.write(freq.get(arr2[i]) + " "); }}// Driver code let arr1 = [ "neveropen", "learn", "for", "egeks", "ealrn" ]; let n = arr1.length; let arr2 = [ "kgees", "rof", "nrael" ]; let m = arr2.length; count(arr1, arr2, n, m); // This code is contributed by souravghosh0416.</script> |
Output
2 1 2
Time Complexity: O(n*plog(p)+m*qlog(q)) where n and m are the sizes of both the array and p and q are the maximum size of string present in arr1 and arr2 respectively.
Auxiliary space: O(n+m).
Another Approach:
- Create a helper function “calculateFrequency” that takes a string and an integer array of size 26 as input. The function should iterate over the string and increment the frequency of each character in the integer array. For example, if the string is “neveropen”, the frequency array should be [1, 0, 0, 0, 2, 0, 0, …, 0] because there is one ‘g’, two ‘e’s, one ‘k’, and one ‘s’.
- Create a function “checkAnagram” that takes two strings as input and returns true if they are anagrams of each other. To check if two strings are anagrams, we can use the “calculateFrequency” function to calculate the frequency arrays for both strings and compare them.
- Create a function “countAnagrams” that takes a string and an array of strings as input and returns the number of strings in the array that are anagrams of the given string. The function should iterate over the array and use the “checkAnagram” function to check if each string is an anagram of the given string.
- In the main function, create two arrays of strings “arr1” and “arr2” and their sizes “n1” and “n2” respectively. Iterate over the strings in “arr2” and call the “countAnagrams” function to count the number of anagrams of each string in “arr1”. Print the count for each string in “arr2”.
Below is the implementation of the above approach:
C++
#include<bits/stdc++.h>using namespace std;// Function to calculate the frequency of characters in a stringvoid calculateFrequency(string str, int *freq) { for(int i=0; i<str.length(); i++) freq[str[i] - 'a']++;}// Function to check if two strings are anagrams of each otherbool checkAnagram(string str1, string str2) { int freq1[26] = {0}, freq2[26] = {0}; calculateFrequency(str1, freq1); calculateFrequency(str2, freq2); for(int i=0; i<26; i++) if(freq1[i] != freq2[i]) return false; return true;}// Function to count the number of anagrams of a string in an arrayint countAnagrams(string str, string *arr, int n) { int count = 0; for(int i=0; i<n; i++) if(checkAnagram(str, arr[i])) count++; return count;}// Function to print the count of anagrams of strings in arr2 that are present in arr1void printAnagramCount(string *arr1, int n1, string *arr2, int n2) { for(int i=0; i<n2; i++) { int count = countAnagrams(arr2[i], arr1, n1); cout<<count<<" "; }}// Driver codeint main() { string arr1[] = {"neveropen", "learn", "for", "egeks", "ealrn"}; string arr2[] = {"kgees", "rof", "nrael"}; int n1 = sizeof(arr1)/sizeof(arr1[0]); int n2 = sizeof(arr2)/sizeof(arr2[0]); printAnagramCount(arr1, n1, arr2, n2); return 0;}// This code is contributed by rudra1807raj |
Java
// Java code for the above approaachimport java.util.Arrays;public class GFG { // Function to calculate the frequency of characters in a string public static void calculateFrequency(String str, int[] freq) { for (int i = 0; i < str.length(); i++) freq[str.charAt(i) - 'a']++; } // Function to check if two strings are anagrams of each other public static boolean checkAnagram(String str1, String str2) { int[] freq1 = new int[26]; int[] freq2 = new int[26]; calculateFrequency(str1, freq1); calculateFrequency(str2, freq2); return Arrays.equals(freq1, freq2); } // Function to count the number of anagrams of a string in an array public static int countAnagrams(String str, String[] arr, int n) { int count = 0; for (int i = 0; i < n; i++) { if (checkAnagram(str, arr[i])) count++; } return count; } // Function to print the count of anagrams of strings in arr2 that are present in arr1 public static void printAnagramCount(String[] arr1, int n1, String[] arr2, int n2) { for (int i = 0; i < n2; i++) { int count = countAnagrams(arr2[i], arr1,n1); System.out.print(count + " "); } } // Driver code public static void main(String[] args) { String[] arr1 = {"neveropen", "learn", "for", "egeks", "ealrn"}; String[] arr2 = {"kgees", "rof", "nrael"}; int n1 = arr1.length; int n2 = arr2.length; printAnagramCount(arr1, n1, arr2, n2); }}// This code is contributed by Utkarsh Kumar |
Python3
# Function to calculate the frequency of characters in a stringdef calculateFrequency(s): freq = [0] * 26 for char in s: freq[ord(char) - ord('a')] += 1 return freq# Function to check if two strings are anagrams of each otherdef checkAnagram(str1, str2): freq1 = calculateFrequency(str1) freq2 = calculateFrequency(str2) return freq1 == freq2# Function to count the number of anagrams of a string in an arraydef countAnagrams(s, arr): count = 0 for item in arr: if checkAnagram(s, item): count += 1 return count# Function to print the count of anagrams of strings in arr2 that are present in arr1def printAnagramCount(arr1, arr2): for item in arr2: count = countAnagrams(item, arr1) print(count, end=" ")# Driver codearr1 = ["neveropen", "learn", "for", "egeks", "ealrn"]arr2 = ["kgees", "rof", "nrael"]printAnagramCount(arr1, arr2) |
Javascript
// Function to calculate the frequency of characters in a stringfunction calculateFrequency(str, freq) { for (let i = 0; i < str.length; i++) { freq[str.charCodeAt(i) - 'a'.charCodeAt(0)]++; }}// Function to check if two strings are anagrams of each otherfunction checkAnagram(str1, str2) { const freq1 = new Array(26).fill(0); const freq2 = new Array(26).fill(0); calculateFrequency(str1, freq1); calculateFrequency(str2, freq2); for (let i = 0; i < 26; i++) { if (freq1[i] !== freq2[i]) { return false; } } return true;}// Function to count the number of anagrams of a string in an arrayfunction countAnagrams(str, arr) { let count = 0; for (let i = 0; i < arr.length; i++) { if (checkAnagram(str, arr[i])) { count++; } } return count;}// Function to print the count of anagrams of strings in arr2 that are present in arr1function printAnagramCount(arr1, arr2) { for (let i = 0; i < arr2.length; i++) { const count = countAnagrams(arr2[i], arr1); console.log(count + " "); }}// Driver codeconst arr1 = ["neveropen", "learn", "for", "egeks", "ealrn"];const arr2 = ["kgees", "rof", "nrael"];printAnagramCount(arr1, arr2); |
Output
2 1 2
Time Complexity: The time complexity of the given code is O(n1n2k), where “n1” is the size of “arr1”, “n2” is the size of “arr2” and “k” is the maximum length of a string in the arrays. This is because the main function calls the “printAnagramCount” function which uses a nested loop to iterate through each string in “arr2″and then for each string, it calls the “countAnagrams” function which has another nested loop to iterate through each string in “arr1”.
Auxiliary Space: The space complexity of the given code is O(k), where “k” is the maximum length of a string in the arrays. This is because the “calculateFrequency” function uses two arrays of size 26 (for each character in the alphabet) to store the frequency of characters in a string. Since the size of these arrays is constant, the space complexity of the code is proportional to the maximum length of a string in the arrays.
Please suggest if someone has a better solution that is more efficient in terms of space and time.
This article is contributed by Aarti_Rathi. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
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!
