Count number of equal pairs in a String in C++

Here we will first understand how to count number of equal pairs in a String using two methods, then we will write a C++ programs to implement these solutions.

Given: A string s

Problem: To find the number of equal pairs in the string s.

Note: Pairs (s[i], s[j]), (s[j], s[i]), (s[i], s[i]), (s[j], s[j]) should be considered different.

Examples:

Input: air
Output: 3
Explanation :
3 pairs that are equal are (a, a), (i, i) and (r, r)

Input : proprogramming
Output : 28

Common Approach: 

  • Run two nested for loops
  • Find out all the possible pairs and keep the count of the pairs.

This approach is not efficient as we have to compare each and every letter with other letter of string and it will become more complex if the string length is suppose more than 100.

Solution using Common Approach:

#include <iostream>
using namespace std;
int main() {
    string s = "proprogramming";
    int count =0;
    for (int i=0; i<s.size(); i++)
        {
            
            for (int j=0; j<s.size(); j++)
                {
                    if (s[j] == s[i])
                    count++;
                }
        }
    cout<<count;
    return 0;
}

OUTPUT:

28

Efficient Approach:

We need to count the number of equal pairs in linear time. Since pairs (x, y) and pairs (y, x) are considered different. We need to use a hash table to store the count of all occurrences of a character. So we know if a character occurs twice, then it will have 4 pairs – (i, i), (j, j), (i, j), (j, i). So using a hash function, store the occurrence of each character, then for each character the number of pairs will be occurrence^2. Hash table will be 256 in length as we have 256 characters.

Solution using Efficient Approach in C++:

#include <bits/stdc++.h> 
using namespace std; 
#define MAX 256 

// Function to count the number of equal pairs 
int countPairs(string s) 
{ 
    // Hash table 
    int cnt[MAX] = { 0 }; 

    // Traverse the string and count occurrence 
    for (int i = 0; i < s.length(); i++) 
        cnt[s[i]]++; 

    // Stores the answer 
    int ans = 0; 

    // Traverse and check the occurrence of every character 
    for (int i = 0; i < MAX; i++) 
        ans += cnt[i] * cnt[i]; 

    return ans; 
} 

int main() 
{ 
    string s = "proprogramming"; 
    cout << countPairs(s); 
    return 0; 
} 

OUTPUT:

28