Count of character pairs at same distance as in english alphabets

Given a string, write a function that will print the number of pairs whose elements are at same distance as in english alphabets

Example

INPUT
s = "agckj"

OUTPUT
3
The pairs are (a,c), (g,j) and (j,k)

Method 1

Tiime Complexity : O()

Algorithm

1. Generate all pairs

2. If in any pair characters are at same distance, then increament the count

Method 2 (Optimized)

Uses the fact that there can be only 26 alphabets

C++ Program

//optimized method
#include<bits/stdc++.h>
#define NO_OF_CHARS 26
using namespace std;
 
//Function to count pairs
int noOfPairs(string s)
{
    int count = 0;
    int n = s.length();
 
    for (int i=0; i<n ; i++)
    {
        // This loop runs at most 26 times
        for (int j=1; (i+j)<n && j<=NO_OF_CHARS; j++)
        {
            if ((abs(s[i+j] - s[i]) == j))
            {
                count++;
            }
        }
    }
    return count;
}
 

int main()
{
    string s = "agckj" ;
    cout << noOfPairs(s)<<endl;
    return 0;
}
Try It

Time Complexity : O(n)

Algorithm

1. Instead of checking an element upto length of the string, check from current index to 26th index

C++ Program

//Brute Force Algo Code
#include<bits/stdc++.h>
using namespace std;
 
// Function to count pairs
int noOfPairs(string s)
{
    int count = 0;
    int n = s.length();
    for (int i = 0 ; i < n ; i++)
    {
        for (int j = i+1; j < n ; j++)
        {
            // If characters are at same distance, increament count
            if (abs(s[i] - s [j]) == abs(i-j))
            {
                count++;
            }
        }
    }     
    return count;
}
 
int main()
{
    string s = "agckj" ;
    cout << noOfPairs(s)<<endl;
    return 0;
}
Try It

 


Next > < Prev
Scroll to Top