Alternate Print

Easy
0/40
Average time to solve is 10m
4 upvotes
Asked in companies
UberBank Of AmericaMAQ Software

Problem statement

You have two strings “A” and “B”. Your task is to print these two strings in an alternative fashion according to indices i.e. first character of “A”, the first character of “B”, the second character of “A”, the second character of “B” and so on.

Note: 
If all characters of one string are printed and some characters of other string are remaining, then you have to print the remaining characters of the other string at the end of the resulting string.
Follow Up : 
Can you solve the problem in O(N) time complexity and O(1) space complexity?
For Example: 
A = “abc” B = “fdh” then answer will be afbdch.
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line of input contains a single integer T, representing the number of test cases or queries to be run. 

Then the T test cases follow.

The first line of each test contains two space-separated strings “A” and “B”.
Output format : 
For each test case, print a single line containing these two strings in an alternative fashion according to indices.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10    
1 <= |A|, |B| <= 10^5 
A and B contains only lower case English characters

Time Limit: 1sec
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Sample Input 1 :
2 
ab the
ac ninjas
Sample Output 1 :
atbhe
ancinjas
Explanation For Sample Input 1:
For the first test case, A = “ab” and B = “the” 
Print the first two characters of both strings in an alternative fashion,
We get “atbh” then finally append "e" to get the answer as “atbhe” 

For the second test case, A = “ac” and B = “ninjas”
Printing first two characters of both strings in alternative fashion, 
We will get “anci”, now append remaining characters to answer. So the answer will be  “ancinjas”.
Sample Input 2 :
1
coding ninjas
Sample Output 2 :
cnoidnijnags
Explanation For Sample Input 2:
For the first test case, A = “coding” and B = “ninjas”
Printing both strings in the alternative fashion we will get “cnoidnijnags”.
Hint

Think of a recursive solution.  

Approaches (2)
Recursive Approach

The idea here is to use recursion and append characters one by one from A and B using a variable turn. If turn equals 0 then append character from A and if turn equals 1 then append character from B to answer. If we have appended all characters from one string, then append the remaining characters of the other string to answer.

 

Steps : 

 

  1. Declare an empty string to store the alternative print order, say the answer.
  2. Declare few variables such as turn, to know whether we need to append character from A or B and indexOfA, indexOfB to get indices of A and B respectively.
  3. Declare a function alter to get alternative print order and store it in answer.
  4. Finally, return the answer.

alter(answer, A, B, indexOfA, indexOfB, turn):

  1. If turn = 0 then the following two cases will occur:
    • If indexOfA >= size of A then appends the remaining characters of B to answer and break the recursion.
    • Else append A[indexOfA] to answer and change turn to 1,add 1 to indexOfA for next recursive call i.e. call alter(answer, A, B, indexOfA + 1, indexOfB, 1).
  2. If turn = 1 then the following two cases will occur:
    • If indexOfB >= size of B then appends the remaining characters of A to answer and break the recursion.
    • Else append B[indexOfB] to answer and change turn to 0, add 1 to indexOfB for next recursive call i.e. call alter(answer, A, B, indexOfA , indexOfB + 1, 0).
Time Complexity

O(N+M), where N and M are the length of string A and B respectively.

 

In the worst case, we are appending each character from A and B which takes O(N+M) time. Hence the overall time complexity will be O(N+M)

Space Complexity

O(N+M), where N and M are the length of string A and B respectively.

 

In the worst case, we need O(N+M) recursion calls. Hence the overall complexity will be O(N+M).

Code Solution
(100% EXP penalty)
Alternate Print
Full screen
Console