Number of index pairs such that s[i] and s[j] are anagrams

0 0 5 minutes read

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 code
int 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 code
public 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 code
if __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 code
public 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:

Time Complexity: O(n² * 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 zambiatek!