Mailing Problem

Easy
0/40
profile
Contributed by
54 upvotes
Asked in companies
Nagarro SoftwareGoogle inc

Problem statement

Dr. Doofenshmirtz is trying to make another big mischief. To prevent this, Major Francis Monogram wants to send mail to Perry the Platypus to inform him about the mischief. He just needs to send a secret message ‘s’ to perry. He has a special keyboard “keyboard” in which all the letters are in a straight line but jumbled. The time taken to move his finger from index ‘i’ to index ‘j’ is |j - i|. He wants to know how much time will it take to send the secret message to Perry.

Note : 
Initially, he is at the first letter of the keyboard.

All letters are in lower-case English letters.
For Example : 
Let s = “perry”, keyboard = “qwertyuiopasdfghjklzxcvbnm”.

Now In this example, Francis will start from the first index and go to ‘p’, which will take 9 seconds, now from ‘p’ to ‘e’, the distance is of 7 indexes, from ‘e’ to ‘r’ the distance is 1, from ‘r’ to ‘r’ it will be zero, and from ‘r’ to ‘y’ the distance will be 2. Hence the total time taken is 9 + 7 + 1 + 0 + 2 = 19.
Hence the answer is 19.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.

The first line of each test case contains a string “keyboard” denoting the keyboard’s layout.

The second line of the test case contains a string ‘s’ denoting the secret message which needs to be sent.
Output Format : 
For each test case, print a single integer “answer”, denoting the time taken by Francis to type the secret message.

Output for each test case will be printed in a separate line.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.
Constraints : 
1 <= T <= 100
keyboard.length = 26
1 <= |S| <= 10^5, where |S| represents the length of the String S.

Time limit: 1 sec
Sample Input 1 :
2
abcdefghijklmnopqrstuvwxyz
abc
zyxwvutsrqponmlkjihgfedcba
zayb
Sample Output 1 :
2
72
Explanation For Sample Output 1 :
For the first test case, Francis is currently on ‘a’ so he does not have to move his fingers for the first letter and then move one index from ‘a’ to ‘b’ and again one index from ‘b’ to ‘c’.
Hence the answer is 2.

For the second test case, he will start from the 0th index and then move to 25 to type ‘a’, then to index 1 to type ‘y’, and at last to index 24 to type ‘b’. Hence the total time taken is 0 + 25 + 24 + 23 = 72.
Sample Input 2 :
2
mvpglaejurowcfbtisdkzhxqny
ferb
bjqtcxmkgzfeowdlsuaypnivrh
phineas
Sample Output 2 :
28
48
Hint

Iterate through the complete keyboard until we find the required character.

Approaches (2)
Naive approach

In this approach, we will start searching every letter from the point where the last letter was located, when we find the next letter we will add the time taken to find the letter to the final answer and return the final answer.

 

The steps are as follows:

  • Take an integer “answer” in which we will store the total time taken to type all the letters and initialize it with 0.
  • Iterate through the string s from 0 to n(say iterator be i):
    • Search for “s[i]” on the keyboard from the current index to both sides of the keyboard, left and right.
    • If “keyboard[j]” = “s[i]” add abs(i-j) to “answer”
  • Return “answer”.
Time Complexity

O( |S| * 26 ), where |S| is the length of the string ‘s’.

 

Since we are iterating through the whole string ‘s’ and searching for the current letter in the string keyboard.

Hence, the total time complexity of this approach will be O( |S| * 26 ).

Space Complexity

O( 1 ).

 

We are not using any extra space.

Hence the space complexity will be O( 1 ).

Code Solution
(100% EXP penalty)
Mailing Problem
Full screen
Console