Given an array s[] of N strings. The task is to find the number of pairs of indices (i, j) such that s[i] is an anagram of s[j].
Examples:
Input: s[] = {“aaab”, “aaba”, “cde”, “dec”}
Output: 2
(“aaab”, “aaba”) and (“cde”, “dec”) are the only valid pairs.Input: s[] = {“ab”, “bc”, “cd”}
Output: 0
Approach: An efficient approach is to sort each string and increase the count of it in a map. For each string in the map, if k is the count of it then (k * (k – 1)) / 2 is the number of valid pairs.
Below is the implementation of the above approach:
C++
// CPP program to find number of pairs of integers// i, j such that s[i] is an anagram of s[j].#include <bits/stdc++.h>using namespace std;// Function to find number of pairs of integers// i, j such that s[i] is an anagram of s[j].int anagram_pairs(vector<string> s, int n){ // To store count of strings map<string, int> mp; // Traverse all strings and store in the map for (int i = 0; i < n; i++) { // Sort the string sort(s[i].begin(), s[i].end()); // Store in the map mp[s[i]]++; } // To store the number of pairs int ans = 0; // Traverse through the map for (auto i = mp.begin(); i != mp.end(); i++) { int k = i->second; // Count the pairs for each string ans += (k * (k - 1)) / 2; } // Return the required answer return ans;}// Driver codeint main(){ vector<string> s = { "aaab", "aaba", "baaa", "cde", "dec" }; int n = s.size(); // Function call cout << anagram_pairs(s, n); return 0;} |
Java
// Java program to find number of pairs of integers// i, j such that s[i] is an anagram of s[j].import java.util.*;class GFG{ // Function to find number of pairs of integers// i, j such that s[i] is an anagram of s[j].static int anagram_pairs(String []s, int n){ // To store count of strings Map<String, Integer> mp = new HashMap<>(); // Traverse all strings and store in the map for (int i = 0; i < n; i++) { // Sort the string char []chArr = s[i].toCharArray(); Arrays.sort(chArr); s[i] = new String(chArr); // Store in the map if(mp.containsKey(s[i])) { mp.put(s[i], mp.get(s[i]) + 1); } else { mp.put(s[i], 1); } } // To store the number of pairs int ans = 0; // Traverse through the map for (Map.Entry<String, Integer> i : mp.entrySet()) { int k = i.getValue(); // Count the pairs for each string ans += (k * (k - 1)) / 2; } // Return the required answer return ans;}// Driver codepublic static void main(String []args){ String [] s = { "aaab", "aaba", "baaa", "cde", "dec" }; int n = s.length; // Function call System.out.println(anagram_pairs(s, n));}}// This code is contributed by 29AjayKumar |
Python3
# Python3 implementation to find # number of pairs of integers i, j # such that s[i] is an anagram of s[j]. # Function to find number of pairs of integers # i, j such that s[i] is an anagram of s[j].def anagram_pairs(s, n): # To store the count of sorted strings mp = dict() # Traverse all strings and store in the map for i in range(n): # Sort the string temp_str = "".join(sorted(s[i])) # If string exists in map, increment count # Else create key value pair with count = 1 if temp_str in mp: mp[temp_str] += 1 else: mp[temp_str] = 1 # To store the number of pairs ans = 0 # Traverse through the map for k in mp.values(): # Count the pairs for each string ans += (k * (k - 1)) // 2 # Return the required answer return ans# Driver codeif __name__ == "__main__": s = ["aaab", "aaba", "baaa", "cde", "dec"] n = len(s) print(anagram_pairs(s, n)) # This code is contributed by AnkitRai01 |
C#
// C# program to find number of pairs of integers// i, j such that s[i] is an anagram of s[j].using System;using System.Collections.Generic;class GFG{ // Function to find number of pairs of integers// i, j such that s[i] is an anagram of s[j].static int anagram_pairs(String []s, int n){ // To store count of strings Dictionary<String, int> mp = new Dictionary<String, int>(); // Traverse all strings and store in the map for (int i = 0; i < n; i++) { // Sort the string char []chArr = s[i].ToCharArray(); Array.Sort(chArr); s[i] = new String(chArr); // Store in the map if(mp.ContainsKey(s[i])) { mp[s[i]] = mp[s[i]] + 1; } else { mp.Add(s[i], 1); } } // To store the number of pairs int ans = 0; // Traverse through the map foreach (KeyValuePair<String, int> i in mp) { int k = i.Value; // Count the pairs for each string ans += (k * (k - 1)) / 2; } // Return the required answer return ans;}// Driver codepublic static void Main(String []args){ String [] s = { "aaab", "aaba", "baaa", "cde", "dec" }; int n = s.Length; // Function call Console.WriteLine(anagram_pairs(s, n));}}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// Javascript program to find number of pairs of integers// i, j such that s[i] is an anagram of s[j].// Function to find number of pairs of integers// i, j such that s[i] is an anagram of s[j].function anagram_pairs(s, n){ // To store count of strings let mp = new Map(); // Traverse all strings and store in the map for (let i = 0; i < n; i++) { // Sort the string let chArr = s[i].split(""); chArr.sort(); s[i] = chArr.join(""); // Store in the map if(mp.has(s[i])){ mp.set(s[i], mp.get(s[i]) + 1) }else{ mp.set(s[i], 1) } } // To store the number of pairs let ans = 0; // Traverse through the map for (let i of mp) { let k = i[1]; // Count the pairs for each string ans += Math.floor((k * (k - 1)) / 2); } // Return the required answer return ans;}// Driver code let s = [ "aaab", "aaba", "baaa", "cde", "dec" ]; let n = s.length; // Function call document.write(anagram_pairs(s, n));// This code is contributed by _saurabh_jaiswal</script> |
Output:
4
Time Complexity: O(n2 * logn)
Auxiliary Space: O(n)
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!
… [Trackback]
[…] Information on that Topic: geeksforgeeks.org/number-of-index-pairs-such-that-s-i-and-s-j-are-anagrams/ […]
… [Trackback]
[…] There you can find 87565 additional Information on that Topic: geeksforgeeks.org/number-of-index-pairs-such-that-s-i-and-s-j-are-anagrams/ […]
… [Trackback]
[…] Info to that Topic: geeksforgeeks.org/number-of-index-pairs-such-that-s-i-and-s-j-are-anagrams/ […]