Last Updated: 20 Apr, 2021
Decoded string
Easy
Asked in company
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’.
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.
Approaches
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.