DEV Community

Brandon Gier
Brandon Gier

Posted on

Cracking the Coding Interview: LeetCode's "Merge Strings Alternately"

One of the problems on the "Leetcode 75" interview preparedness set is the Merge Strings Alternately problem. In this problem, solvers are tasked with merging 2 strings together, one letter at a time, to form a new one.
We can look at an example to better understand this problem:
Word 1: "Aa"
Word 2: "Bb"
Our resulting string here should be "ABab".


This problem fits into 2 general types of problems when you solve it. First, it's a string manipulation problem. These can be relatively common in interviews due to them typically being slightly easier to explain to candidates. The other category this problem falls into is the general category of "Two pointer" problems. These problems are ones which are best solved by maintaining 2 references to locations in a data structure, such as lists or strings. The key to solving these types of problems is understanding when a given pointer needs to move and change its spot.


So, how do you solve this problem? Let's start by deciding what to do with each step. Because want to alternate letters in the string, we recognize we need to maintain 3 separate pieces of data. First, which letter we're at in the first string. Second, which letter we're at in the second string. Third, which string we need to look at.
index1, index2 = 0, 0
word = 0

We can use word as an even or odd to determine which word we want to work off of.
Once we have these in place, it's a simple matter of alternating the word we pull a letter off of and constructing the string. In the end, one valid solution can look like this:

class Solution:
def mergeAlternately(self, word1: str, word2: str) -> str:
resultString = ""
index1, index2 = 0, 0
count = 0
while index1 < len(word1) and index2 < len(word2):
if count % 2 == 0:
resultString += word1[index1]
index1 += 1
else:
resultString += word2[index2]
index2 += 1
count += 1
if index1 < len(word1):
resultString += word1[index1:]
elif index2 < len(word2):
resultString += word2[index2:]
return resultString

Top comments (0)