Merge Strings Alternately LeetCode 1768

LeetCode 1768 asks you to merge two strings by alternating their characters, starting with the first character of word1. You pick one character from word1, then one from word2, then back to word1, and so on until one string is exhausted.

When one string runs out of characters before the other, you simply append all remaining characters of the longer string to the end of your merged result. This tail-append step is what makes the problem require careful boundary handling.

The problem is straightforward conceptually but is an excellent foundation for understanding the two-pointer merge pattern used in harder problems like merge sorted arrays and merge intervals.

The standard approach uses two pointers: i for word1 and j for word2. In each iteration, you append word1[i] if i is still within bounds, then word2[j] if j is still within bounds, advancing each pointer independently.

Because the two pointers advance independently, the loop naturally handles the case where one string is shorter. When i reaches len(word1), you stop adding characters from word1 but continue adding from word2 until j is also exhausted.

This single-loop approach is cleaner than separate loops because it handles equal-length, word1-longer, and word2-longer cases uniformly without special branching at the loop level.

The single loop runs while either pointer is still valid (i < len1 or j < len2). Inside the loop, two independent if-statements check whether each pointer is still in bounds before appending that character and advancing its pointer.

This avoids the need for a separate "append remaining" phase after the loop. Both strings' remaining characters are handled organically as the loop continues after the shorter string runs out.

The result list is joined at the end into a string. Using a list and a final join is the correct approach — string concatenation inside a loop creates O(n^2) total copies due to string immutability in Python and Java.

Python's itertools.zip_longest pairs characters from word1 and word2, using fillvalue="" for the shorter string's missing positions. Joining all characters from the pairs gives the merged string in one expression.

The one-liner is: "".join(c for pair in zip_longest(word1, word2, fillvalue="") for c in pair). This is idiomatic Python but obscures the mechanics — interviewers may not immediately recognize what it does.

Both approaches produce identical results. The zip_longest version is elegant for production code; the explicit two-pointer loop is better for demonstrating algorithmic understanding in an interview setting.

Example 1: word1="abc", word2="pqr". Both strings have length 3. The merge proceeds: (a,p), (b,q), (c,r). Result: "apbqcr". No tail to append since both strings exhaust simultaneously.

Example 2: word1="ab", word2="pqrs". word2 is longer. The merge takes (a,p), (b,q) — both pointers advance. Then word1 is exhausted (i=2 = len(word1)). The loop continues with only j: append r, then s. Result: "apbqrs".

Example 3: word1="abcd", word2="pq". word1 is longer. Merge takes (a,p), (b,q). Then word2 is exhausted. Loop continues with only i: append c, then d. Result: "apbqcd".

Python solution: result = []; i = j = 0; while i < len(word1) or j < len(word2): then two independent if blocks appending word1[i] and word2[j] with bounds checks. Return "".join(result). Time: O(m+n), Space: O(m+n) for the result list.

Java solution: StringBuilder sb = new StringBuilder(); int i = 0, j = 0; while (i < word1.length() || j < word2.length()) — same two independent if blocks with charAt(). Return sb.toString(). StringBuilder's append is amortized O(1), making the total O(m+n).

Both solutions share the same asymptotic complexity: O(m+n) time to process all characters, O(m+n) space for the output. There is no sub-optimal version of this algorithm since you must read every character at least once.

Merge Strings Alternately is the gateway to the string merge family. GCD of Strings (LeetCode 1071) asks whether two strings share a repeating divisor unit — related because both problems analyze structure across two strings simultaneously.

Longest Common Prefix (LeetCode 14) finds the shared beginning across multiple strings. Merge Two Sorted Lists (LeetCode 21) uses the same two-pointer advance pattern but with a comparison step to determine which pointer to advance — the key difference from this problem.

For harder merge problems, Merge Intervals (LeetCode 56) and Merge k Sorted Lists (LeetCode 23) build on the same pointer-per-sequence idea. Understanding Merge Strings Alternately's simple uniform-advance pattern makes the conditional-advance logic in sorted merges easier to grasp.