Merge Strings Alternately

Problem

Given two strings word1 and word2, merge them by alternating characters: first a character from word1, then one from word2, then word1 again, and so on. If one string is exhausted before the other, append the remaining characters of the longer string. Return the merged string.

Examples

• word1 = "abc", word2 = "pqr" → "apbqcr" Equal lengths: characters alternate throughout, a-p, b-q, c-r.
• word1 = "ab", word2 = "pqrs" → "apbqrs" word1 runs out after two rounds; the remaining "rs" of word2 is appended.
• word1 = "abcd", word2 = "pq" → "apbqcd" word2 runs out first; "cd" from word1 finishes the string.

Constraints

• 1 <= word1.length, word2.length <= 100
• Both strings consist of lowercase English letters.

Think about it first

TL;DR

One shared index over both strings (two-pointer merge) — O(m + n) time, O(m + n) space for the output.

Approach 1 — Brute force: build with string concatenation

The direct translation of the statement: walk both strings, appending characters to a result string with +=.

def mergeAlternately(word1: str, word2: str) -> str:
    result = ""
    i = j = 0
    while i < len(word1) and j < len(word2):
        result += word1[i]
        result += word2[j]
        i += 1
        j += 1
    result += word1[i:]
    result += word2[j:]
    return result

• Time: worst case O((m + n)^2) — Python strings are immutable, so each += may copy the whole result so far (CPython sometimes optimizes this in-place, but you can’t rely on it).
• Space: O(m + n).

At length ≤ 100 this passes, but the quadratic copying becomes a real problem on larger inputs. Prefer the list-buffer form below.

Approach 2 — Two pointers into a list buffer

Both the “still merging” and “leftover tail” phases follow the same rule: at position i, take word1[i] if it exists, then word2[i] if it exists. One index serves as both pointers, and appending to a list then joining once avoids the quadratic copying.

def mergeAlternately(word1: str, word2: str) -> str:
    parts: list[str] = []
    for i in range(max(len(word1), len(word2))):
        if i < len(word1):
            parts.append(word1[i])
        if i < len(word2):
            parts.append(word2[i])
    return "".join(parts)

Walkthrough on word1 = "ab", word2 = "pqrs" (loop runs i = 0..3):

Join → "apbqrs". The tail case needed no special code.

• Time: O(m + n) — each character appended exactly once, single join.
• Space: O(m + n) for the buffer/output.

Approach 3 — zip_longest one-liner

Pairing up positions and padding the shorter side is exactly what itertools.zip_longest does; padding with the empty string makes the missing side contribute nothing to the join. This is the same algorithm as Approach 2, expressed declaratively.

from itertools import zip_longest


def mergeAlternately(word1: str, word2: str) -> str:
    return "".join(a + b for a, b in zip_longest(word1, word2, fillvalue=""))

Walkthrough on word1 = "abcd", word2 = "pq": zip_longest yields ("a","p"), ("b","q"), ("c",""), ("d",""); the pairs concatenate to "ap" + "bq" + "c" + "d" → "apbqcd".

• Time: O(m + n).
• Space: O(m + n).

Common pitfalls

• Stopping the loop at min(len(word1), len(word2)) and forgetting to append the longer string’s tail.
• Appending the tail of the wrong string (or both tails unconditionally without slicing from the right index).
• Building the answer with repeated string += on large inputs — accidentally quadratic; collect into a list and "".join once.
• Starting with word2 instead of word1 — the order is fixed by the statement.

Pattern takeaway

Two-pointer merges (as opposed to converging pointers) advance one cursor per input and emit in a fixed priority order; when the cursors can desynchronize only by exhaustion, a single shared index plus existence checks is the cleanest form. Handle the leftover tail by making “source is exhausted” contribute nothing rather than writing a separate post-loop phase.