Given a string s, find the number of pairs of characters that are same. 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 : geeksforgeeks
Output : 31
The naive approach will be you to run two nested for loops and find out all pairs and keep a count of all pairs.
Steps to implement-
- Find the size of the given string
- Initialize a variable let us say “ans” with value 0 to store the answer
- Run two nested “for loop” from 0 to the size of string-1
- In that nested loop if two pair of characters are the same then increment that “ans” by 1
- In last return or print the value stored in “ans”
Code-
C++
#include <bits/stdc++.h>
using namespace std;
int countPairs(string s)
{
int n = s.size();
int ans = 0;
for ( int i = 0; i < n; i++) {
for ( int j = 0; j < n; j++) {
if (s[i] == s[j]) {
ans++;
}
}
}
return ans;
}
int main()
{
string s = "geeksforgeeks" ;
cout << countPairs(s);
return 0;
}
|
Java
public class Main {
public static int countPairs(String s) {
int n = s.length();
int ans = 0 ;
for ( int i = 0 ; i < n; i++) {
for ( int j = 0 ; j < n; j++) {
if (s.charAt(i) == s.charAt(j)) {
ans++;
}
}
}
return ans;
}
public static void main(String[] args) {
String s = "geeksforgeeks" ;
System.out.println(countPairs(s));
}
}
|
Python
def countPairs(s):
n = len (s)
ans = 0
for i in range (n):
for j in range (n):
if s[i] = = s[j]:
ans + = 1
return ans
if __name__ = = "__main__" :
s = "geeksforgeeks"
print (countPairs(s))
|
C#
using System;
public class GFG
{
public static int CountPairs( string s)
{
int n = s.Length;
int ans = 0;
for ( int i = 0; i < n; i++)
{
for ( int j = 0; j < n; j++)
{
if (s[i] == s[j])
{
ans++;
}
}
}
return ans;
}
public static void Main( string [] args)
{
string s = "geeksforgeeks" ;
Console.WriteLine(CountPairs(s));
}
}
|
Javascript
function countPairs(s)
{
let n = s.length;
let ans = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (s[i] == s[j]) {
ans++;
}
}
}
return ans;
}
let s = "geeksforgeeks" ;
console.log(countPairs(s));
|
Output-
31
Time Complexity: O(N2), because of two nested loops
Auxiliary Space: O(1), because no extra space has been used
For an 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.
Below is the implementation of the above approach :
C++
#include <bits/stdc++.h>
using namespace std;
#define MAX 256
int countPairs(string s)
{
int cnt[MAX] = { 0 };
for ( int i = 0; i < s.length(); i++)
cnt[s[i]]++;
int ans = 0;
for ( int i = 0; i < MAX; i++)
ans += cnt[i] * cnt[i];
return ans;
}
int main()
{
string s = "geeksforgeeks" ;
cout << countPairs(s);
return 0;
}
|
C
#include <stdio.h>
#define MAX 256
int countPairs( char s[])
{
int cnt[MAX] = { 0 };
for ( int i = 0; s[i] != '\0' ; i++)
cnt[s[i]]++;
int ans = 0;
for ( int i = 0; i < MAX; i++)
ans += cnt[i] * cnt[i];
return ans;
}
int main()
{
char s[] = "geeksforgeeks" ;
printf ( "%d" ,countPairs(s));
return 0;
}
|
Java
import java.io.*;
class GFG {
static int MAX = 256 ;
static int countPairs(String s)
{
int cnt[] = new int [MAX];
for ( int i = 0 ; i < s.length(); i++)
cnt[s.charAt(i)]++;
int ans = 0 ;
for ( int i = 0 ; i < MAX; i++)
ans += cnt[i] * cnt[i];
return ans;
}
public static void main (String[] args)
{
String s = "geeksforgeeks" ;
System.out.println(countPairs(s));
}
}
|
Python 3
MAX = 256
def countPairs(s):
cnt = [ 0 for i in range ( 0 , MAX )]
for i in range ( len (s)):
cnt[ ord (s[i]) - 97 ] + = 1
ans = 0
for i in range ( 0 , MAX ):
ans + = cnt[i] * cnt[i]
return ans
if __name__ = = "__main__" :
s = "geeksforgeeks"
print (countPairs(s))
|
C#
using System;
class GFG {
static int MAX = 256;
static int countPairs( string s)
{
int []cnt = new int [MAX];
for ( int i = 0; i < s.Length; i++)
cnt[s[i]]++;
int ans = 0;
for ( int i = 0; i < MAX; i++)
ans += cnt[i] * cnt[i];
return ans;
}
public static void Main ()
{
string s = "geeksforgeeks" ;
Console.WriteLine(countPairs(s));
}
}
|
Javascript
<script>
const MAX = 256
function countPairs(s){
let cnt = new Array(MAX).fill(0)
for (let i=0;i<s.length;i++)
cnt[s.charCodeAt(i) - 97] += 1
let ans = 0
for (let i = 0; i < MAX; i++)
ans += cnt[i] * cnt[i]
return ans
}
let s = "geeksforgeeks"
document.write(countPairs(s))
</script>
|
Time Complexity: O(n), where n is the length of the string
Auxiliary Space: O(n), where n is the length of the string
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 geeks!