Home » Interview Questions » String Interview Questions » Count of character pairs at same distance as in english alphabets

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

 

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions