Encoded Letter

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
2 upvotes
Asked in company
Google inc

Problem statement

Kevin got an encoded letter from his friend in which all occurrences of a word (say, ‘X’) is replaced by another word (say, ‘R’). This letter is very confidential and that’s why his friend directly calls him and tell him the words ‘X’ and ‘R’. But, Kevin is not able to decode the letter and so, he wants your help as he believes in you.

All you have to do is to replace all occurrences of the word ‘X’ with the word ‘R' in the given letter.

Note:

You are provided with the content written in the letter. The content of the letter will only contain the English alphabets, non-negative integers, and white spaces. It is guaranteed that the content will have the first character as the English alphabet or a non-negative integer.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a single integer ’T’ representing the number of test cases. 

The first line of each test case will contain the string ‘S’ which represents the content written in the given letter.

The second line of each test case will contain the string ‘X’ which represents the word ‘X’.

The third line of each test case will contain the string ‘R’ which represents the word ‘R’.
Output Format: 
For each test case, return the decoded content of the given letter or we can say return the new content of the letter in which all occurrences of the word ‘X’ is replaced by the word ‘R’.
Note: 
You don’t need to print anything, It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 50
1 <= |S| <= 10^4
1 <= |X| <= |S|
1 <= |R| <= |S|

Where '|S|', '|X|', '|R|' denotes the length of the string 'S', 'X', 'R' respectively.

Time limit: 1 sec
Sample Input 1:
2
COD00G N00JAS 00DIA
00
IN
Welcome to oooo Studio
oooo
Code
Sample Output 1:
CODING NINJAS INDIA
Welcome to Code Studio
Explanation of Sample Output 1:
In test case 1, the decoded content is “CODING NINJAS INDIA”.

In test case 2, the decoded content is “Welcome to Code Studio”.
Sample Input 2:
3
AabB
1
B
abababa
aba
a
aaab
aa
11
Sample Output 2:
AabB
aba
11ab
Explanation for Sample Output 2:
In test case 1, the decoded content is “AabB”.

In test case 2, the decoded content is ‘aba’.

In test case 3, the decoded content is “11ab”.
Hint

Iterate over the content and keep replacing the word ‘X’ with ‘R’.

Approaches (2)
Brute Force

The basic idea is to iterate through the content and whenever find the word ‘X’ just replace it with the word ‘R’. We will not be going to change the string that represents the content instead of that we create another string to store the decoded content.

 

The steps are as follows:

 

  1. Create a variable (say, ‘DECODE’) of string type to store the decoded string.
  2. Iterate through the given content ( say, iterator = ‘i’ )
    • Check, the first character of the word ‘X’ and the character of content at ‘i’ is the same and also check ‘i’ + length of the word is less than the length of content. If these conditions are true -
      • Iterate through the given content in forwarding direction from ‘i’ to ‘i’ + length of word ‘X’.
      • If the complete word matches with the word ‘X’, then insert the word ‘R’ into the ‘DECODE’ string.
      • Else, insert the word that appears in the content in this range.
    • Else, insert the character into the ‘DECODE’ string.
  3. Return the string ‘DECODE’.
Time Complexity

O(N * K), Where ‘N’ is the length of the given string 'S' and ‘K’ is the length of the given string ‘X’.

 

Since we are iterating through each character of the string S once and for each character we are matching it with the string X, so the overall time complexity will be O(N * K).

Space Complexity

O(N), Where ‘N’ is the length of the given content.

 

Since we are using an additional string to store the decoded string, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Encoded Letter
Full screen
Console