Last Updated: 3 Sep, 2021
Mailing Problem
Easy
Asked in companies
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.
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
Approaches
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”.
In this approach, we will store all the positions of the keyboard in a map/Vector of size 26 and while iterating through the string ‘s’, we will calculate the distance between the previous letter and the current letter using this map/vector.
The steps are as follows:
- Take a vector “position” of size 26, in which we will store the position of every element of the string “keyboard”.
- Take two integers “answer” and “previous” in which we will store the total time taken to type all the letters and the position of the last element we encountered in the string ‘s’, respectively.
- Iterate through the string “keyboard” from 0 to 26(say iterator be i):
- Update “position[“keyboard[i]” - ‘a’]” = ‘i’.
- Iterate through the string s from 0 to n(say iterator be i):
- Increment “answer” by abs(position[s[i] - ‘a’ ] - “previous”).
- Update “previous” = “position[s[i] - ‘a’]”.
- Return “answer”.