Alternate Print
Last Updated: 7 Jan, 2021
Difficulty: Easy
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 :
- Declare an empty string to store the alternative print order, say the answer.
- 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.
- Declare a function alter to get alternative print order and store it in answer.
- Finally, return the answer.
alter(answer, A, B, indexOfA, indexOfB, turn):
- 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).
- 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).
Approach 2
The idea here is to run a loop and append characters from A and B one by one until both of them are not empty, then append the remaining characters of the non-empty string to answer.
Steps :
- Declare an empty string to store the alternative print order, say the answer.
- Run a loop from index = 0 to a minimum of size of A and size of B, and do:
- Append A[index] to answer then append B[index] to answer.
- After running the loop if the size of A is greater than the size of B then append the remaining characters of A to answer, else append the remaining characters of B to answer.
- Finally, return the answer.
