Hackerrank certification question

general
1

An anagram of a string is another string with the same characters in the same frequency, in any order. For example ‘abc’, ‘acb’,‘bca’,‘cab’,‘cba’,‘bac’ all are anagrams of ‘abc’.Given two arrays of strings, for every string in one list, determine how many anagrams of it are in the other list.
Write a function that receives dictionary and query, two string arrays. It should return an array of integers where each element 'i’contains the number of anagrams of query[i] that exist in dictionary.

Example

dictionary = [‘hack’, ‘a’, ‘rank’,‘khac’,‘ackh’, ‘kran’,‘rankhacker’, ‘a’, ‘ab’, ‘bo’, ‘stairs’, ‘raits’]

query = [“a”, “nark”, “bs”, “hack”, “stair”)

query[0] =“a” has 2 anagrams in dictionary: ‘a’ and ‘a’.

query[1]= “nark” has 2 anagrams in dictionary: ‘rank’ and ‘kran’.

query[2] = “bs” has 0 anagrams in dictionary

query[3] = “hack” has 3 anagrams in dictionary. ‘hack’, ‘khac’ and ‘ackh’.

query[4] = “stair” has 1 anagram in dictionary: ‘raits’

While the characters are the same in stairs, the frequency of 's’differs, so it is not an anagram.

The final answer is [2, 2, 0, 3, 1].

stringAnagram has the following parameters:

string dictionary[n]: an array of strings to search

in
string query[q]: an array of strings to search for

Returns

int[q]: an array of integers where the value is the answer to query[i].

Constraints

• 1<= length(dictionary), length(query) <= 10^5

• Every string consists of lowercase English letters.

2
  1. Sort every string in dictionary.
  2. Put the strings in a map, say mp.
  3. Run a loop on the query array, and sort the string, suppose S. Print mp[S]
    Overall complexity- O(N*logN)
3

Can you please provide with the solution because I tried in similar manner and it was throwing TLE in 6 test cases but solved 6 test cases.

5
Code 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
#define ll long long int
void solve(){
	ll n,m;
	cin>>n>>m;
	 vector<string>v(n),v1(m);
	 ll i;
	 map<string,ll>mp;
	 for(i=0;i<n;i++){
		 cin>>v[i];
		 sort(v[i].begin(),v[i].end());
		 mp[v[i]]++;
	 }
	 vector<ll>ans;
	 for(i=0;i<m;i++){
		 cin>>v1[i];
		 sort(v1[i].begin(),v1[i].end());
		 ans.push_back(mp[v1[i]]);
	 }
	 for(auto it:ans){
		 cout<<it<<" ";
     }
}
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll t=1;
   // cin>>t;
    while(t--){
		solve();
	}
}
2 Likes
6

check this out.

7

Thank you so much…

8

Thank you so much

9

worked?

2 Likes
10

Yes

1 Like
11

Could you please share the python code for this same challenge, it would be really appreciated…

12

Could you please share the python code for this same challenge, it would be really appreciated…

13 
def solve(arr,query):
	dict={}
	for s in arr:
		i=str(sorted(s))
		if i in dict:
			dict[i]+=1
		else:
			dict[i]=1
	ans=[]
	for s in query:
		i=str(sorted(s))
		if i in dict:
			ans.append(dict[i])
		else:
			ans.append(0)
	return ans

arr=[i for i in input().split()]
query=[i for i in input().split()]

print(*solve(arr,query))
2 Likes
14

Thank you so much :slight_smile: :slightly_smiling_face:

15 
package contest.hackerrank.basic;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created using IntelliJ IDEA. Author:  abhijeet, Date:    30/01/22, Time:    7:21 PM
 */
public class Anagram {

  public static void main(String[] args) {
    Anagram anagram = new Anagram();
    List<String> dictionary = Arrays.asList("heater", "cold", "clod", "reheat", "docl");
    List<String> query = Arrays.asList("codl", "heater", "abcd");
    System.out.println(anagram.stringAnagram(dictionary, query));
  }

  private List<Integer> stringAnagram(List<String> dictionaryList, List<String> queryList) {
    List<Integer> answer = new ArrayList<>();
    Map<String, Integer> dictMap = new HashMap<>();
    dictionaryList.forEach(dict -> {
      char tempArray[] = dict.toCharArray();
      Arrays.sort(tempArray);
      String sortedDict = new String(tempArray);
      if (dictMap.containsKey(sortedDict)) {
        dictMap.put(sortedDict, dictMap.get(sortedDict) + 1);
      } else {
        dictMap.put(sortedDict, 1);
      }
    });
    queryList.forEach(query -> {
      char tempArray[] = query.toCharArray();
      Arrays.sort(tempArray);
      String sortedQuery = new String(tempArray);
      int count = 0;
      if (dictMap.containsKey(sortedQuery)) {
        count = dictMap.get(sortedQuery);
      }
      answer.add(count);
    });
    return answer;
  }
}
1 Like