Alternate Print

Posted: 7 Jan, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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.
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.
Approach 1

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).
Try Problem