Convert Sentence

Easy

0/40

Average time to solve is 15m

Contributed by

20 upvotes

Asked in companies

Problem statement

You are given a sentence in the form of a string ‘S’. You have to convert ‘S’ into its equivalent mobile numeric keypad sequence, i.e. print the sequence in such a way that if it is typed on the given keypad, the output should be the string ‘S’. A keypad for the reference is shown below.

Note:

1. There will be only lower case letters.
2. There will not be any special characters or capital letters in the input string.
3. There will be no spaces in the string.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of the input contains an integer T denoting the number of test cases.
The first line of each test case contains one integer N, denoting the length of the string ‘S’.
The second line of each test case contains the input string ‘S’.

Output Format:

The only line of output of each test case consists of an output string, denoting the pattern which is required to print ‘S’. 
The output of each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 3000

Where 'T' is the number of test cases and ' N' is the length of the sentence 'S'.

Sample Input 1:

2
12
codingninjas
1
f

Sample Output 1:

22266634446646644466527777
333

Explanation for Sample Output 1:

For the first test case, for ‘c’ we have to press 2 three times, for ‘o’ we have to press 6 three times and so on. Hence we get the desired output.

For the second test case, to type the letter ‘f’, we can press 6 three times.

Hint 1

Try to write how many times we have to press a particular key to get a character.

Approaches (1)

Approach 1

Implementation

The simplest possible approach is to write how many times we have to press a particular key to get a character.
For each character, we can store what should be typed on the keypad. We can store this information in a string array named ‘freq’.
The size of freq[] will be 26 and index 0 will store the pattern for ‘a’, index 1 will store the pattern for ‘b’ and so on.. Index 25 will store the pattern for ‘z’.
The pattern for ‘a’ is 2, for ‘z’ is 9999, for ‘n’ is 66 and so on.
After storing the pattern in the array, we will take an output string and while traversing the string and we will get the pattern corresponding to the current character from the freq array and add it to our output string.

Time Complexity

O(N), where N is the size of the string

Since we are traversing the string only once. Also, filling the ‘freq’ array takes O(26) time. Thus, the final time complexity is O(26 + N) = O(N).

Space Complexity

O(26).

Since we are storing the frequency pattern for each character and there can only be 26 unique characters in the given string.

(100% EXP penalty)

Convert Sentence

Console