Merge Strings Alternately - Video Solutions

Problem Overview: You are given two strings and must build a new string by alternating characters from each. Start with the first character of word1, then word2, and continue until one string runs out. Append the remaining characters from the longer string at the end.

Approach 1: Iterative Merge with Indices (O(n + m) time, O(1) extra space)

This approach walks through both strings using two indices. Start with i = 0 for word1 and j = 0 for word2. On each step, append word1[i] if i is still within bounds, then append word2[j] if j is valid. Increment the corresponding pointer after each append. The process continues until both pointers reach the end of their strings.

The key insight is that alternating order is deterministic. There is no need for extra data structures or backtracking. You simply iterate forward and append characters as you go. Once one string is exhausted, the loop still checks the other pointer and continues appending remaining characters.

This pattern is essentially a simplified form of the two pointers technique where each pointer advances independently through its sequence. Because each character is processed exactly once, the runtime is O(n + m) where n and m are the lengths of the two strings. Extra space remains O(1) aside from the output buffer. This is the most common and practical solution and is supported in C, C++, Java, Python, C#, and JavaScript.

Approach 2: Recursive Approach (O(n + m) time, O(n + m) space)

The recursive version models the alternating merge as repeated subproblems. At each step, take the first character of word1 and the first character of word2, append them, and recursively process the remaining substrings. If either string becomes empty, return the other string as the base case.

The recursion naturally enforces the alternating pattern because every call consumes one character from each string. Conceptually this solution is elegant: each call reduces the problem size until one string is exhausted.

However, recursion adds call stack overhead. Each recursive call stores state on the stack, leading to O(n + m) auxiliary space in the worst case. For languages without tail call optimization, this approach is less memory‑efficient than iteration. The logic still revolves around basic string operations such as slicing or indexing.

Recommended for interviews: The iterative two‑pointer solution is what interviewers expect. It demonstrates clear control of indices, efficient iteration, and awareness of linear time complexity. Showing the recursive idea can illustrate problem decomposition, but the iterative approach better reflects practical coding patterns for two pointer style string problems.