Table of Contents
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.