Merge Strings Alternately
Understanding the Problem
We have two strings and need to weave them together character by character, alternating between them. Take the first character from word1, then the first from word2, then the second from word1, then the second from word2, and so on.
The complication is that the strings might not be the same length. When one string runs out, we append whatever remains of the longer string. This is a zip that does not stop when the shorter input ends.
The core of the problem is iterating up to the length of the longer string and taking a character from each string at every index where one exists.
Key Constraints:
1 <= word1.length, word2.length <= 100→ Both inputs are short, and the lengths bound the output: the merged string has exactlyword1.length + word2.lengthcharacters. The natural solution is a single linear pass.word1andword2consist of lowercase English letters → Both strings are non-empty, so there is always at least one character to place.
Approach 1: Two Pointers (Process Both, Then Append Remainder)
Intuition
Handle the merge in two phases. First, walk through both strings together for as long as both have characters, alternating one character from word1 and one from word2. Once the shorter string runs out, append whatever remains from the longer one.
This matches the plain description of the task: take turns picking from each string until one runs out, then append the rest.
Algorithm
- Initialize an empty result (using a
StringBuilderor equivalent). - Use a pointer
istarting at 0. - While
iis less than the length of bothword1andword2: - Append
word1[i]to the result. - Append
word2[i]to the result. - Increment
i. - If
word1has remaining characters (from indexionward), append them all. - If
word2has remaining characters (from indexionward), append them all. - Return the result as a string.
Example Walkthrough
Code
- Time Complexity: O(n + m). We visit every character in both strings exactly once. The first loop runs min(n, m) times, and the remainder loops cover the leftover characters.
- Space Complexity: O(n + m). The result string holds all characters from both inputs. No extra data structures beyond the output.
This is optimal in time and space. The three separate loops can collapse into one, which the next approach does.
Approach 2: Single Loop (Optimal and Cleaner)
Intuition
Instead of splitting the work into an interleave phase and a remainder phase, do it in one loop. Iterate from i = 0 up to the maximum of the two lengths. At each step, if word1 has a character at index i, add it; if word2 has a character at index i, add it.
This handles unequal lengths through the bounds checks alone. When one string runs out, its check fails at the remaining indices and the loop keeps adding from the other string, so no separate remainder logic is needed.
The order of the two if statements is required. Checking word1 before word2 at each index places the word1 character first, matching the rule to start with word1. Swapping the two checks would emit the word2 character first at every index and produce the wrong string.
Algorithm
- Initialize an empty result (using a
StringBuilderor equivalent). - Find the maximum length:
maxLen = max(len(word1), len(word2)). - For
ifrom0tomaxLen - 1: - If
i < len(word1), appendword1[i]. - If
i < len(word2), appendword2[i]. - Return the result as a string.
Example Walkthrough
Code
- Time Complexity: O(n + m). The loop runs max(n, m) times, and inside each iteration we do O(1) work. Total characters processed is exactly n + m.
- Space Complexity: O(n + m). The result string stores all characters from both inputs. No additional data structures are used.