1768. Merge Strings Alternately - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

You are given two strings word1 and word2. Merge the strings by adding letters in alternating order, starting with the first string (word1). If one string is longer than the other, append the additional letters onto the end of the merged string. Return the merged string.

Examples:

Example 1:

Input: word1 = "abc", word2 = "pqr"
Output: "apbqcr"
Explanation: The letters from word1 and word2 are merged alternately.

First take 'a' from word1, then 'p' from word2, then 'b' from word1, and so on. The merged result is "apbqcr".

Example 2:

Input: word1 = "ab", word2 = "pqrs"
Output: "apbqrs"
Explanation: word2 is longer, so after alternating "apbq", the remaining "rs" from word2 are appended at the end.

Example 3:

Input: word1 = "abcd", word2 = "pq"
Output: "apbqcd"
Explanation: word1 is longer, so after alternating "apbq", the remaining "cd" from word1 are appended at the end.

Constraints:

1 <= word1.length, word2.length <= 100
word1 and word2 consist of lowercase English letters .

Hints

Hint 1: Try using two pointers (or indices) to iterate through both strings at the same time. On each step, take one character from word1, then one from word2, and so on.
Hint 2: Determine the length of the shorter string. You can loop that many times to alternate characters, then handle any remaining part of the longer string by appending it to the result.
Hint 3: Consider using a loop that runs while there are characters left in either string. In each iteration, if there’s a character available from word1, append it, and if there’s a character from word2, append it. This approach naturally covers the case where one string ends before the other.

Multiple Approaches

Brute Force Approach

A straightforward way to solve this problem is to iterate through both strings character by character and build the merged string. We can use a loop to alternate between word1 and word2 until one of them is exhausted.

For example, append word1[0], then word2[0], then word1[1], word2[1], and so on.

Once we reach the end of one string, we append the remaining part of the other string to the result. This approach directly follows the problem description and is easy to implement.

How this works: We initialize an empty result (e.g., an empty string or list). Then use an index i for word1 and j for word2.

In a loop, alternate between adding word1[i] and word2[j] to the result and incrementing the indices. When one index reaches the end of its string, break out of the alternating loop and concatenate the rest of the other string.

We can implement this by checking bounds at each step or by looping a fixed number of times (like the length of the shorter string) and then handling leftovers. The brute force approach is essentially what the problem expects: directly simulate the merging process character by character.
This approach is intuitive but if implemented naively (for example, repeatedly using string concatenation for each character in certain languages), it could be less efficient. However, given the problem's small input size constraints, even a direct implementation will run comfortably within time limits.

Optimal Approach (Two-Pointer, Space-Efficient)

The optimal solution follows the same basic idea as the brute force approach, but with attention to efficiency in implementation (especially in languages where string concatenation is expensive).

The most efficient approach uses two pointers and builds the result using a buffer (like a list or StringBuilder) rather than concatenating strings in each iteration. This avoids excessive intermediate string creation and is more space-efficient in practice.

Key Idea: Use a single loop that runs until you have processed all characters from both strings. In each iteration:

Append the next character from word1 to the result if word1 still has characters left.
Append the next character from word2 to the result if word2 still has characters left.
Move the pointers forward accordingly.

By using a dynamic buffer (list in Python or StringBuilder in Java), we accumulate characters and then join or convert to a string at the end. This approach ensures we only create the final string once, achieving optimal time and space usage.

It cleanly handles the scenario when one string ends earlier – the loop condition (checking both i < len(word1) or j < len(word2)) naturally allows the remaining characters of the longer string to be appended after the other is exhausted.

Why it’s optimal: In terms of big-O complexity, this approach does the minimum necessary work – it visits each character of each string exactly once.

There are no nested loops or repeated scans, and no expensive operations outside of the single pass.

Memory usage is proportional to the length of the output (which is unavoidable since we have to store the merged string), and no significant extra storage is used besides the output buffer.

Comparison of Approaches

Both the brute force and the optimal approach ultimately have to read all characters of both input strings and produce an output string of length len(word1) + len(word2).

Therefore, time complexity for both is linear in the total length of the input (O(n), where n is the length of the longer string or roughly m + n for inputs of length m and n). The space complexity for both is also O(m+n) due to the output string that must be constructed.

The main difference lies in implementation details:

The brute force approach, if written carelessly, might perform string concatenation in each step. In some languages, immutable string concatenation can lead to higher constant time costs (e.g., in Java or Python, doing result += char in a loop creates many temporary strings). It’s conceptually simple but can be slightly suboptimal in practice.
The optimal approach uses proper data structures (like list or StringBuilder) to accumulate the result, which improves the constant factors and avoids potential performance issues. This is more of a best practice refinement than a different algorithm. The logic is the same, but we ensure that we're not doing any redundant work.

In summary, both approaches run in linear time and use linear space, which is optimal for this problem given that we must output all characters.

The “optimal” solution is simply a cleaner and more efficient implementation of the brute-force idea, especially important in languages where string handling needs care.

Code Implementation

Python Implementation

Python3

. . . .

Explanation: We use two indices i and j to traverse word1 and word2. The while loop runs as long as either string has characters left.

In each iteration, we check i against len(word1) and j against len(word2) to decide whether to take a character from word1 and/or word2. This handles the case when one string is shorter – once i reaches the end of word1, the if i < len(word1) check will fail and no more characters from word1 will be added (but we might still add from word2, and vice versa).

We collect characters in a list and then join them at the end for efficiency. The resulting string is returned.

(Alternate Python one-liner solution for reference:) Python’s itertools.zip_longest can be used to pair characters and fill missing values when lengths differ. For example:

Python3

. . . .

This does the same as above by zipping the strings and using an empty string as filler for the shorter one. We use it here just to showcase a Pythonic approach; in an interview, the two-pointer method shown earlier is perfectly fine and clear.

Java Implementation

Java

. . . .

Explanation: We use a StringBuilder to efficiently build the merged string character by character. Two indices i and j track our position in word1 and word2. The while loop continues until we've consumed both strings. Inside, we check if there's a character available at word1[i] and append it, then do the same for word2[j]. This automatically handles uneven lengths. Finally, result.toString() gives the merged result. Using StringBuilder.append is recommended over string concatenation in a loop for Java, to avoid creating many intermediate String objects.

Complexity Analysis

Time Complexity: Both approaches run in linear time O(n), where n is the total number of characters we need to process. More precisely, if m = len(word1) and n = len(word2), the time complexity is O(m + n). We are essentially iterating through each character of both strings once. There are no nested loops or expensive operations beyond this single pass. For example, if word1 and word2 are each 100 characters long (the max allowed), our loops will run at most 100 + 100 = 200 iterations. This is very efficient.

Space Complexity: The space complexity is O(m + n) as well, which comes from the storage for the merged output string. We need to allocate a new string (or buffer) to hold the merged result because we are combining two strings. Apart from the output, we use a few fixed-size variables (indices and maybe a few extra chars), so auxiliary space (not counting the output) is O(1). If building the string in a list or StringBuilder, that structure will at most hold m+n characters before we convert it to the final string.

It’s worth noting that this is the minimum space required, since the output itself has m+n characters. We cannot do better than O(m+n) space because we have to output all those characters. Both the brute force and optimal implementations meet this space requirement. The optimal implementation just ensures we don't create excessive temporary strings during the process.

Comparison: In terms of big-O, both approaches are the same (linear time, linear space). The difference is mostly in constant factors and clarity. For instance, building the result using a StringBuilder in Java or a list in Python (and joining) is more memory-efficient than repeatedly concatenating strings in a loop. But asymptotically, the complexity remains linear, which is optimal for this problem size. Given the constraint that each input string is at most 100 characters, even a straightforward method is plenty fast (100 characters is trivial for modern computers). However, practicing efficient string building is good for general coding habits and becomes crucial for larger inputs.

Step-by-Step Walkthrough with Visual Examples

Let’s walk through an example to see how the merging works step by step. Consider Example 2 with word1 = "ab" and word2 = "pqrs":

word1:  a    b
word2:  p    q    r    s

We will merge these strings alternately:

Start: i = 0, j = 0, merged = "" (empty string initially).
Step 1: Take word1[i] = 'a' and append to merged → merged = "a". Now take word2[j] = 'p' and append → merged = "ap". (Now merged string is "ap"). Increment i and j (now i = 1, j = 1).
- Visual: after this step, we have a from word1 and p from word2 combined: merged: a p
Step 2: i = 1, j = 1. Take word1[1] = 'b' → merged = "apb". Then take word2[1] = 'q' → merged = "apbq". (Merged string is now "apbq"). Increment i and j (i = 2, j = 2).
- Visual: now merged has a p b q which corresponds to taking "ab" and "pq" alternately.
Now i = 2, which equals len(word1) (word1 is fully used up), and j = 2 while len(word2) = 4. We exit the alternating loop because one string (word1) has no more characters to alternate.
Append remainder: Since word1 is done but word2 still has characters left (j = 2 and word2 length is 4), we append the remaining substring of word2 starting from index 2. The remaining part of word2 is "rs" (characters at indices 2 and 3). We add "rs" to the merged string. Now merged = "apbqrs".
Result: The final merged string is "apbqrs", which matches the expected output.

Throughout this process, we added letters in alternating order: a (from word1), p (from word2), b (from word1), q (from word2), and then once word1 ran out, we just took the rest of word2 (r and s). This step-by-step construction ensures the relative order of characters from each original word is preserved, and one character from each word is placed one after the other. You can visualize the merge as interleaving two sequences like a zipper:

word1: a   b
word2: p   q   r   s
merged: a p b q r s

Similarly, if we walk through Example 3 (word1 = "abcd", word2 = "pq"), the alternating steps would produce "apbq" and then the remaining "cd" from word1 gets appended, resulting in "apbqcd". In each case, the algorithm cleanly handles the uneven lengths by appending the leftover part of the longer string at the end.

This approach works for all cases, including when one string is empty (in which case the merged result is just the other string, since there’s nothing to alternate from the empty one), or when they are the same length (in which case characters will alternate until both end simultaneously).

Common Mistakes and Edge Cases

When implementing this problem, developers might run into a few pitfalls. Here are some common mistakes and how to avoid them:

Forgetting to handle leftover characters: A frequent mistake is to only loop for the length of the shorter string and forget to append the remaining part of the longer string afterwards. If one input is longer, those extra characters need to be included at the end of the result. Always check after the loop if one of the indices is not at the end of its string, and append the remainder.
Off-by-one errors in loops: If using a single loop with a complex condition or trying to be clever with index arithmetic, it’s easy to accidentally go out of bounds. For instance, one might try to use a single index to alternately index into two strings (by using modulo or increment logic) and run into trouble when one string ends. A safer approach is to use two indices and straightforward loop conditions (as shown in our solutions). Make sure your loop stops when it should – either when both strings are fully traversed, or use a condition within the loop to break when one string ends.
Not truly alternating on each iteration: Some solutions attempt to alternate by toggling a flag each loop iteration (e.g., using one loop and switching between adding from word1 and word2). If not managed carefully, this can lead to adding two characters from the same string in one iteration or other logic bugs. It’s simpler to structure the loop to add one char from each string per iteration (when available), as this inherently alternates correctly. If you do use separate conditions for two strings in one loop (like our approach), ensure you do not use if-else between them – use separate if statements so that in each iteration you can add both a word1 char and a word2 char if both are available. Using else by mistake would skip the second string’s character on iterations where the first string still had characters.
Inefficient string concatenation: In languages like Java, doing result = result + char in a loop is a common mistake which leads to O(n^2) time due to strings being immutable. In Python, repeatedly doing result += char is not as costly for small strings, but for larger strings it can also become slow. The fix is to use a buffer (StringBuilder in Java, list in Python) and join at the end, as we showed. Given the input size here (max 100 chars each), this isn’t a big performance issue, but it’s a good habit to avoid this mistake for larger problems.

Now let's consider some edge cases and ensure our solution covers them:

Empty Strings: If word1 is "" (empty) and word2 is non-empty, the merged result should just be word2 (and vice versa if word2 is empty). Our loop handles this because if one string is length 0, the loop will simply append characters from the other. Make sure your code doesn’t assume non-empty strings.
One Character Strings: If each string has length 1, say word1 = "x", word2 = "y", the result should be "xy". This is a trivial case of alternating. Similarly, if one is one character and the other is longer, e.g. word1 = "x", word2 = "hello", result should be "xhello" (the single character from word1 followed by all of word2). The logic of adding remaining characters covers this.
Strings of Equal Length: e.g. word1 = "abc", word2 = "def". Here, the loop will alternate all characters (output "adbecf"). Both pointers will finish at the same time and there will be no remainder to append. Ensure the logic works when both run out together (our loop condition while i<len1 or j<len2 and each if inside handles this elegantly).
First String Longer: e.g. word1 = "ABCDE", word2 = "xy". After alternating to form "AxBy", the remainder "CDE" from word1 should be appended giving "AxByCDE". Our code checks for i < len(word1) after the loop (or continues in the loop since j will hit end and i still < len1) and appends the rest.
Second String Longer: e.g. word1 = "hi", word2 = "JKLMN". The result should be "hJ iK LMN" -> actually merging: "hJiKLMN" where "LMN" is the leftover from word2. Our approach appends the remainder of word2 in this scenario.

By thinking through these cases (empty, unequal lengths, equal lengths), you can confidently cover all situations. The provided solution is robust against all these edge cases.

Alternative Variations

This problem is a specific instance of merging or interleaving sequences. Interviewers may twist it or relate it to similar scenarios:

Merge More Than Two Strings: A variation could involve three or more strings to merge in alternating order (round-robin fashion). The concept is similar, but you would cycle through the strings taking one character from each in turn. This is a generalization of alternating merge. For example, merging three strings "aa", "bbb", "cccc" alternately might yield "a b c a b c c c ..." in cyclic order. The logic would extend by looping until all strings are exhausted, taking from each if available in each cycle.
Zigzag Iterator (Two or k Lists): Instead of strings, you might be asked to alternate elements from two arrays or linked lists. LeetCode has a problem called Zigzag Iterator (Problem 281) where given two lists, the goal is to output their elements alternately. For example, input lists [1,2] and [3,4,5,6] should produce output sequence [1,3,2,4,5,6] . A follow-up to that problem asks for extending the approach to k lists (multiple lists) in a cyclic fashion. The solution uses a queue or index cycling, but the idea of taking turns from each list is analogous to this string problem.
Interleaving String Check: Another related problem is LeetCode 97: Interleaving String, which doesn’t ask you to merge the strings but to check if a given third string is a interleaving (shuffle merge) of two other strings. In other words, it asks if you can form the third string by alternating characters from the first two (not strictly every other, but maintaining the order of characters from each). The problem states: given s1, s2, and s3, determine whether s3 is formed by an interleaving of s1 and s2. This is a harder problem (usually solved with dynamic programming) but conceptually related to merging strings.
Merging Linked Lists Alternately: You might encounter a linked list variation where you have two linked lists and are asked to weave them together by nodes. For instance, taking two linked lists and merging them so that nodes from each list alternate in the resulting list. The approach would be similar: take a node from list1, then list2, and so on, adjusting pointers. This is a common operation when manipulating lists.
Merge Two Sorted Lists vs Alternate Merge: It’s worth noting the difference between this problem and merging two sorted lists (like the classic LeetCode 21). In merging sorted lists, you choose elements based on their values to maintain sorted order. In alternating merge (our problem), you ignore values and strictly take turns. The problem we solved is simpler in that you don't have to compare elements, just alternate them. Both are good to practice because they involve manipulating two sequences simultaneously. For further practice, you can try LeetCode 21: Merge Two Sorted Lists, which is another fundamental merging problem.

Related Problems for Practice:

LeetCode 281: Zigzag Iterator – Implement an iterator that outputs elements from two (or more) lists in alternating order.
LeetCode 97: Interleaving String – Given three strings, check if the third is an interleaving of the first two (more advanced, involves DP).
LeetCode 21: Merge Two Sorted Lists – Merge two linked lists by sorting, a different kind of merge but good for understanding handling two data streams.
LeetCode 1669: Merge In Between Linked Lists – A linked list problem where a portion of one list is merged into another (not alternating, but involves merging concept).

Each of these problems touches on combining two sequences or checking combinations, which helps reinforce the concept of traversal with multiple pointers and careful condition handling.

By practicing such problems, you build a strong intuition for managing multiple iterators/pointers, which is a common theme in many coding interview questions.