Interleave Strings
Given two strings, write a program to merge the given two strings by adding characters in alternating order, starting with the first string. If a string is longer than the other, append the additional characters onto the end of the merged string.Input
The first line of input will contain a string.
The second line of input will contain a string.
The strings may contain special characters, digits and letters.Output
The output should be the merged stringExplanation
For example, if the given strings are "abc" and "pqrs", then alternating characters from each string are merged as "a" from "abc", "p" from "pqr", "b" from "abc" and so on ..., resulting in the merged string "apbqcr".
Sample Input 1
abc
pqr
Sample Output 1
apbqcr
Sample Input 2
abc
pqrst
Sample Output 2
apbqcrst
Interleave Strings
Given two strings, write a program to merge the given two strings by adding characters in alternating order, starting with the first string. If a string is longer than the other, append the additional characters onto the end of the merged string.Input
The first line of input will contain a string.
The second line of input will contain a string.
The strings may contain special characters, digits and letters.Output
The output should be the merged stringExplanation
For example, if the given strings are "abc" and "pqrs", then alternating characters from each string are merged as "a" from "abc", "p" from "pqr", "b" from "abc" and so on ..., resulting in the merged string "apbqcr".
Half an hour ago, my friend and coauthor of the textbook “Coffee Break NumPy” asked me the following question via WhatsApp:
- Problem Formulation
- Alternative 1: First String s1 is Shorter
- Alternative 2: Any String May Be Longer
- Alternative 3: Using External Libraries
- Performance Measurements
- Where to Go From Here?
Problem Formulation
How would you solve the problem of interleaving two strings in Python:
- Input: String
s1= "AAA"and strings2 = "BBBBB" - Output: String
s="ABABABBB"
Being obsessed with finding the most Pythonic way of writing any code snippet [preferably within a single line of code], I quickly became frustrated because there doesn’t seem to be a very simple, clean, and concise answer to this question.
How to Interleave Two Strings of Variable Lengths [Python]?
However, in this article, you’ll learn a robust and easy-to-understand way of solving this problem [without external library support]. So keep on reading.
Alternative 1: First String s1 is Shorter
Assuming the first string is shorter gives us the opportunity to solve the problem in a Python one-liner using list comprehension:
s1 = "AAA" s2 = "BBBBB" s = "".join[[s1[i] + s2[i] for i in range[len[s1]]]] + s2[len[s1]:] print[s] # ABABABBB
Because of Python’s efficient implementation of list comprehension, this option is extremely fast — I doubt that there is anything faster [which is still equally readable].
We combine every
character of the shorter string s1 with the character of the longer string s2 at the respective position. This results in the partially interleaved string "ABABAB". Now, we simply concatenate this with the remaining characters of the longer string s2.
However, this solution doesn’t work if string
s1 can also be longer than string s2.
Why? Because the Python interpreter will raise an Index Erroras accessing s2[i] is not possible.
Alternative 2: Any String May Be Longer
If you don’t assume that one of the string is longer than the other, the problem becomes slightly harder. Still, there is a simple and clean solution to this problem [without using external libraries]. It’s not in a single line of code, but it’s readable, fast, and it doesn’t need any length assumptions:
s1 = "AAA"
s2 = "BBBBB"
s = list[s2]
for i,c in enumerate[s1]:
s.insert[i*2,c]
print["".join[s]]
# ABABABBBFirst, we convert the string s2 to a
list of characters using the list[...] function. This is the basis of our solution.
Second, we insert the characters of the string s1 at positions 0, 2, 4, … by iterating over all
indices i and characters c of the first string s1. Now we insert the characters into every other position of the list.
Alternative 3: Using External Libraries
Expert coders heavily use external libraries because it makes their code more readable, more efficient, and shorter. What’s wrong with that? Here is what an expert reader David of my [free] “Coffee Break Python” email course proposed:
import itertools s1 = "AAA" s2 = "BBBBB" s = "".join[[ x + y for x, y in itertools.zip_longest[s1, s2, fillvalue=""]]] print[s] # ABABABBB
The problem with taking the built-in zip[] function is that the number of pairs returned by the zip[] function is equal to the shorter
iterable.
Here is what my loyal reader David argues:
[…] zip_longest[] vaults the [built-in] zip[]‘s ‘limitation’ of cutting-off at the shorter len[] […]. It ‘extends’ the shorter
iterable with a fillvalue parameter – using [the empty string] rather than the default None, otherwise the subsequent string concatenation will fail!
Again, if library support is allowed [in other words: you are not in a coding interview], this is my preferred solution.
Performance Measurements
After publishing this article, my coauthor Lukas [book “Coffee Break NumPy”] came back to me with a nice performance analysis. Which function performs best? I don’t want to hold the interesting results back because you may find them valuable, too:
import itertools
import matplotlib.pyplot as plt
plt.xkcd[]
def interleave_strings_listcomprehension[s1, s2]:
return "".join[[s1[i] + s2[i] for i in range[len[s1]]]] + s2[len[s1]:]
def interleave_strings_enumerate[s1, s2]:
s = list[s2]
for i, c in enumerate[s1]:
s.insert[i*2, c]
return "".join[s]
def interleave_strings_slicing[s1, s2]:
length_s1 = len[s1]
length_s2 = len[s2]
if length_s1 != length_s2:
if length_s1 > length_s2:
spaces_count = length_s1 - length_s2
s2 = s2 + spaces_count * ' '
else:
spaces_count = length_s2 - length_s1
s1 = s1 + spaces_count * ' '
interleaved = len[s1] * 2 * ['']
interleaved[::2] = s1
interleaved[1::2] = s2
return ''.join[interleaved].replace[' ', '']
def interleave_strings_zip[s1, s2]:
length_s1 = len[s1]
length_s2 = len[s2]
if length_s1 != length_s2:
if length_s1 > length_s2:
spaces_count = length_s1 - length_s2
s2 = s2 + spaces_count * ' '
else:
spaces_count = length_s2 - length_s1
s1 = s1 + spaces_count * ' '
return "".join[i + j for i, j in zip[s1, s2]].replace[' ', '']
def interleave_zip_itertools[s1, s2]:
import itertools
return "".join[[ x + y for x, y in itertools.zip_longest[s1, s2, fillvalue=""]]]
import time
multiplicator = 1000
s1 = multiplicator * "AAA"
s2 = multiplicator * "BBBB"
# Test 1
start = time.perf_counter[]
interleave_strings_listcomprehension[s1, s2]
end = time.perf_counter[]
plt.bar[1,end - start, hatch=" ", label="List comprehension [Alt 1]"]
# Test 2
start = time.perf_counter[]
interleave_strings_enumerate[s1, s2]
end = time.perf_counter[]
plt.bar[2,end - start, hatch="o", label="Enumerate [Alt 2]"]
# Test 3
start = time.perf_counter[]
interleave_strings_slicing[s1, s2]
end = time.perf_counter[]
plt.bar[3,end - start, hatch="+", label="Slicing"]
# Test 4
start = time.perf_counter[]
interleave_strings_zip[s1, s2]
end = time.perf_counter[]
plt.bar[4,end - start, hatch="/", label="Zip"]
# Test 5
start = time.perf_counter[]
interleave_zip_itertools[s1, s2]
end = time.perf_counter[]
plt.bar[5,end - start, hatch="-", label="Zip Itertools [Alt 3]"]
plt.xticks[[],[]]
plt.ylabel["nanosecs"]
plt.legend[]
plt.tight_layout[]
plt.savefig["plot.jpg"]
plt.show[]
Here is the resulting bar plot comparing the runtime of the different functions:
The
slicing function outperformed any other function by at least 50%! I knew that slicing is fast but this result blew my mind. I have also tested the result for even larger strings but slicing still seems to be the fastest alternative. It comes at the cost that readability suffers a bit compared to the itertools
solution.
Where to Go From Here?
If you feel like you have a good solution that will be interesting for the readers of this article, leave a comment below with your solution!
Being able to quickly understand and write source code is a crucial skill of every single coder. Companies such as Amazon, Google, and Facebook are famously interviewing every applicant — testing their understanding and proficiency with source code. Nowadays, understanding Python code fast is one of the most valuable skills you can have as an ambitious coder.
To help you attain this valuable skill, we’ve created the “Coffee Break Python” book series. Check them out!
While working as a researcher in distributed systems, Dr. Christian Mayer found his love for teaching computer science students.
To help students reach higher levels of Python success, he founded the programming education website Finxter.com. He’s author of the popular programming book Python One-Liners [NoStarch 2020], coauthor of the Coffee Break Python series of self-published books, computer science enthusiast, freelancer, and owner of one of the top 10 largest Python blogs worldwide.
His passions are writing, reading, and coding. But his greatest passion is to serve aspiring coders through Finxter and help them to boost their skills. You can join his free email academy here.