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.