1768. Merge Strings Alternately - Detailed Explanation

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, with m = len(word1) and n = len(word2), the time complexity is O(m + n). The loop reads each character of both strings once. There are no nested loops or expensive operations beyond this single pass. When word1 and word2 each hold 100 characters, the maximum allowed, the loop runs at most 100 + 100 = 200 iterations.

Space complexity: The space complexity is O(m + n) as well, and it comes from the storage for the merged output string. Combining two strings requires a new string, or a buffer, to hold the result. Apart from the output, the code keeps only a few fixed size variables, so auxiliary space is O(1). A list or a StringBuilder holds at most m+n characters before the conversion to the final string.

This is the minimum space required, because the output itself has m+n characters. No solution can beat O(m+n) space while returning every character. Both the brute force and the optimal implementation meet that bound. The optimal one also avoids excess temporary strings along the way.

Comparison: In big-O terms the two approaches match, with linear time and linear space. The difference lies in constant factors and clarity. Building the result in a Java StringBuilder or a Python list, then joining once, uses less memory than repeated concatenation in a loop. The asymptotic cost stays linear either way, which is optimal at this problem size. Each input string holds at most 100 characters, so even a plain method is fast. Efficient string building is still worth practicing, because it matters on larger inputs.

Step-by-step walkthrough with visual examples

Let us 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:

1. Start: i = 0, j = 0, merged = "", an empty string.
2. Step 1: Take word1[i] = 'a' and append it to merged, so merged = "a". Now take word2[j] = 'p' and append it, so merged = "ap". Increment i and j, which gives i = 1 and j = 1.
   • Visual: after this step we have a from word1 and p from word2 combined: merged: a p
3. Step 2: i = 1, j = 1. Take word1[1] = 'b', so merged = "apb". Then take word2[1] = 'q', so merged = "apbq". Increment i and j, which gives i = 2 and j = 2.
   • Visual: merged now holds a p b q, which is "ab" and "pq" taken alternately.
4. Now i = 2, which equals len(word1), so word1 is fully used up, while j = 2 and len(word2) = 4. We exit the alternating loop because word1 has no more characters to alternate.
5. Append remainder: word1 is done, and word2 still has characters left, since j = 2 and the length of word2 is 4. We append the remaining substring of word2 starting from index 2. That remaining part is "rs", the characters at indices 2 and 3. Now merged = "apbqrs".
6. 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, then q from word2. Once word1 ran out, we took the rest of word2, which is r and s. This step-by-step construction preserves the relative order of the characters inside each original word, and it places one character from each word one after the other. The merge interleaves the two sequences position by position:

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

Walk through Example 3 the same way, with word1 = "abcd" and word2 = "pq". The alternating steps produce "apbq", then the remaining "cd" from word1 is appended, which gives "apbqcd". In each case the algorithm handles the uneven lengths by appending the leftover part of the longer string at the end.

This approach works for the remaining cases too. When one string is empty, the merged result is just the other string, because the empty one contributes nothing to alternate. When both strings have the same length, the characters alternate until the two indices end at the same time.

Common mistakes and edge cases

A few mistakes come up often in this question. Here is how to avoid them:

• Forgetting to handle leftover characters: A frequent mistake is to loop only for the length of the shorter string and skip the remaining part of the longer one. If one input is longer, those extra characters still belong at the end of the result. After the loop, check whether either index stopped short of its string, then append the remainder.

• Off-by-one errors in loops: A single loop with a complicated condition or clever index arithmetic goes out of bounds easily. One common attempt indexes both strings from one counter with modulo logic, then breaks down when the first string ends. Two indices and straightforward loop conditions are safer, as in the solutions above. Confirm that your loop stops when it should, either when both strings are fully traversed, or at a condition inside the loop that breaks when one string ends.

• Not truly alternating on each iteration: Some solutions toggle a flag on each pass and switch between adding from word1 and word2. Handled loosely, the flag lets two characters from the same string enter in one iteration, or introduces other logic bugs. Adding one character from each string per iteration, when available, is simpler and alternates correctly by construction. With two separate conditions in one loop, as in our approach, do not join them with if-else. Use two independent if statements, so a single iteration can add a word1 character and a word2 character when both are available. An else would skip the character from the second string whenever the first string still had one.

• Inefficient string concatenation: In a language such as Java, result = result + char inside a loop leads to O(n^2) time, because strings are immutable and every concatenation copies. In Python, result += char is cheap on short strings and slow on long ones. The fix is a buffer, a StringBuilder in Java or a list in Python, joined at the end, as we showed. The inputs here hold at most 100 characters each, so the cost is small, and the habit still matters on larger problems.

Now consider some edge cases and confirm that our solution covers them:

• Empty strings: If word1 is "" and word2 is not empty, the merged result should be word2, and the reverse holds when word2 is empty. Our loop handles this, because a string of length 0 simply contributes nothing while characters from the other arrive. Make sure your code does not assume non-empty strings.
• One character strings: If each string has length 1, say word1 = "x" and word2 = "y", the result should be "xy". That is the trivial case of alternating. If one string is a single character and the other is longer, say word1 = "x" and word2 = "hello", the result should be "xhello". The logic that adds the remaining characters covers this.
• Strings of equal length: Take word1 = "abc" and word2 = "def". Here the loop alternates all characters and outputs "adbecf". Both pointers finish at the same time, and there is no remainder to append. Check that your logic works when both run out together, which the loop condition while i < len1 or j < len2 and the two inner checks handle cleanly.
• First string longer: Take word1 = "ABCDE" and word2 = "xy". After alternating to form "AxBy", the remainder "CDE" from word1 should be appended, which gives "AxByCDE". Our code checks i < len(word1) after the loop, or keeps going inside the loop because j hits the end while i is still below len1, and appends the rest.
• Second string longer: Take word1 = "hi" and word2 = "JKLMN". The result should be "hJiKLMN", where "LMN" is the leftover from word2. Our approach appends that remainder.

Thinking through these cases, empty, unequal lengths, and equal lengths, covers every situation. 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 vary it or relate it to similar scenarios:

• Merge more than two strings: A variation could involve three or more strings to merge in alternating, round-robin order. The concept is similar, but you cycle through the strings and take one character from each in turn. This generalizes the alternating merge. For example, merging "aa", "bbb", and "cccc" in cyclic order yields "abcabcbcc". The first two rounds take one character from each string, the third round skips the exhausted "aa", and the final round draws only from "cccc". The logic extends by looping until all strings are exhausted, taking from each one that still has a character in every 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 two lists are given and the goal is to output their elements alternately. For example, the input lists [1,2] and [3,4,5,6] should produce the output sequence [1,3,2,4,5,6]. A follow-up asks you to extend the approach to k lists in a cyclic fashion. That solution uses a queue or index cycling, and 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 does not ask you to merge the strings but to check whether a given third string is an interleaving, or shuffle merge, of two other strings. It asks whether you can form the third string by alternating characters from the first two, not strictly every other character, 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. That is a harder problem, usually solved with dynamic programming, and 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. Nodes from each list then alternate in the resulting list. The approach is similar: take a node from list1, then one from list2, and so on, adjusting pointers as you go. This is a common operation when manipulating lists.

• Merge two sorted lists versus alternate merge: Note the difference between this problem and merging two sorted lists, as in the classic LeetCode 21. When merging sorted lists, you choose elements by value to maintain sorted order. In an alternating merge, our problem, you ignore values and strictly take turns. The problem we solved is simpler, because you never compare elements, you only alternate them. Both are good to practice, because they involve manipulating two sequences at once. For further practice, try LeetCode 21: Merge Two Sorted Lists, another fundamental merging problem.

Related problems for practice:

• LeetCode 281: Zigzag Iterator, which asks you to implement an iterator that outputs elements from two or more lists in alternating order.
• LeetCode 97: Interleaving String, which gives three strings and asks whether the third is an interleaving of the first two. It is more advanced and involves dynamic programming.
• LeetCode 21: Merge Two Sorted Lists, which merges two linked lists by value. It is a different kind of merge, and good for understanding how to handle two data streams.
• LeetCode 1669: Merge In Between Linked Lists, a linked list problem where a portion of one list is merged into another. It does not alternate, but it exercises the merging concept.

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

Two more questions from the same array and string group are Reverse Words in a String and Product of Array Except Self. Both reward the same index discipline that this merge needs. The two pointers pattern and the other techniques that recur across these questions are taught in Grokking the Coding Interview.

Practicing such problems builds a strong intuition for managing multiple pointers at once, which is a common requirement in coding interview questions.