Decoded string

Easy
0/40
Average time to solve is 15m
profile
Contributed by
0 upvote
Asked in company
Adobe

Problem statement

An encoded string ‘S’ is given. To find and write the decoded string to a tape, the encoded string is read one character at a time, and the following steps are taken:

If the character read is a letter, that letter is written onto the tape. If the character read is a digit (say ‘D’), the entire current tape is repeatedly written (D - 1) more times in total.

Now, for some encoded string S and an index (K - 1), find and return the ‘K-th’ letter (0 indexed) in the decoded string.

For example:

Given:- 'S' = “codingninjas”, ‘K’ = 5

The output will be 'n'.
Since the character at the kth index is S[4] = ‘n’.
Detailed explanation ( Input/output format, Notes, Images )

Input format :

The first line of input contains an integer ‘T’ denoting the number of test cases.

The following ‘T’ lines contain a string ‘S’ and an integer ‘K.’

Output format :

For each test case, print a single line containing a single character denoting the ‘K-th’ letter (0 indexed) in the decoded string.

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 <= |S| <= 100
1 <= K <= |S| * |S|

Where ‘T’ is the total number of test cases, and ‘|S|’ is the length of the string and ‘K’ is the number given.

Time limit: 1 sec.

Sample Input 1 :

2
codingninjas 5
code2it 7

Sample Output 1 :

n 
d

Explanation of the Sample Input 1:

For the first test case :  
The output will be 'n'.
Since the character at the k’th index is S[4] = ‘n’.

For the second test case : 
The output will be ‘d’.
Since the final string would be codecodeit.

Sample Input 2 :

2
pro3player4 12
noob2player 8

Sample Output 2 :

a
b
Hint

Can we traverse the string and change the length of the decoded string as and when needed?

Approaches (1)
Iterative approach

The main idea is when a decoded string is equal to some word with some length repeated some number of times, the answer is the same for the index ‘K’ as it is for the index K % length.

  • Find the total size of the string and store it in a variable ‘SIZE’.
  • For each character traverse the string and if the character is a digit multiply the size by digit.
  • Start iterating from the last position i.e. ‘N’ - 1 :
    • Do ‘K’ % ‘SIZE’.
    • If ‘K’ == 0 and the ith letter is an alphabet return that alphabet as the answer.
    • If the ith character is a digit, divide ‘SIZE’ by the digit.
    • Else reduce ‘SIZE’ by 1.
  • If we exit the loop, return the ‘K’th index letter.
Time Complexity

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

 

Since we are just traversing the string twice the net time complexity is O(|S|).

Space Complexity

O(1).

 

Since we are not using any extra space to keep track of elements.

Code Solution
(100% EXP penalty)
Decoded string
Full screen
Console