Count the Pairs at Same Distance as in English Alphabets


Difficulty Level Easy
Frequently asked in Adobe Amazon Dropbox GE Healthcare OYO Rooms
String

Problem Statement

In the “Count of Pairs at Same Distance as in English Alphabets” problem we have given a string “s”. Write a program that will print the number of pairs whose elements are at the same distance as in English alphabets.

Input Format

The first line containing the given string “s”.

Output Format

The first and only one line containing an integer value which denote the number of pairs whose elements are at the same distance as in English alphabets.

Constraints

  • 1<=|s|<=10^6
  • s[i] must be a lower case latter english alphabet

Example

agckj
3

Explanation: Here we can see the distance between the pairs (a,c), (g,j) and (j,k) are same distance as in English alphabets.

Approach – Brute Force

Algorithm

1. Set ans to zero.

2. Run first for loop from 0 to n-1.

3. Inside the first for loop run second for loop from i+1 to n-1.

4. Now, check the distance between indices of these pair is equal to the distance in English alphabets.

5. If in any pair characters are at the same distance, then increment the ans by one.

6. After traversing all the pair print value of ans.

Implementation

C++ program to Count the Pairs at Same Distance as in English Alphabets

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;
    int n=s.length();
    int ans=0;
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            if(abs(s[i]-s[j]) == abs(i-j))
            {
                ans++;
            }
        }
    }
    cout<<ans<<endl;
}

Java program to Count the Pairs at Same Distance as in English Alphabets

import static java.lang.Math.abs;
import java.util.Scanner;

class sum
{       
  public static void main(String[] args) 
  { 
    Scanner sr = new Scanner(System.in); 
                String s = sr.next();
                int n=s.length();
                int ans=0;
                for(int i=0;i<n;i++)
                {
                    for(int j=i+1;j<n;j++)
                    {
                        if(abs(s.charAt(i)-s.charAt(j)) == abs( i-j))
                        {
                            ans++;
                        }
                    }
                }
                System.out.println(ans);
  } 
} 
jqvdqwydvwaekufybwaekfyuawekf
13

Complexity Analysis to Count of Pairs at Same Distance as in English Alphabets

Time Complexity

O(n*n) where n is the size of the string “s”. Here we check for every pair and check the condition if condition is true then increase our answer.

Space Complexity

O(1) because we don’t create any auxiliary space here.

Approach – Optimal

Algorithm

1. Set ans to zero.

2. Run first for loop from 0 to n-1.

3. Inside the first for loop run second for loop from 1 to (i+j) where j is less than or equal 26.

4. Now, checkĀ  the distance between “i+j”th char ans “i”th char.

5. If the distance between them is “j” then increment the ans by one.

6. After completing both for loops, print value of ans.

Implementation

C++ program to Count of Pairs at Same Distance as in English Alphabets

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;
    int n=s.length();
    int ans=0;
    for(int i=0;i<n;i++)
    {
        for(int j=1;i+j<n && j<=26;j++)
        {
            if(abs(s[i+j]-s[i]) == j)
            {
                ans++;
            }
        }
    }
    cout<<ans<<endl;
}

Java program to Count of Pairs at Same Distance as in English Alphabets

import static java.lang.Math.abs;
import java.util.Scanner;

class sum
{       
  public static void main(String[] args) 
  { 
    Scanner sr = new Scanner(System.in); 
                String s = sr.next();
                int n=s.length();
                int ans=0;
                for(int i=0;i<n;i++)
                {
                    for(int j=1;i+j<n && j<=26;j++)
                    {
                        if(abs(s.charAt(i+j)-s.charAt(i)) == j)
                        {
                            ans++;
                        }
                    }
                }
                System.out.println(ans);
  } 
} 
sdvwkudvwduv
5

Complexity Analysis

Time Complexity

O(n) where n is the size of the string “s”. Here we run two for loop first loop run n times and second loop run at most 26 times.

Space Complexity

O(1) because we don’t create any auxiliary space here.

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions