Merge Strings Alternately
Problem
Given two strings word1 and word2, return a new string formed by merging the characters of word1 and word2 alternately. If one string is longer, append the remaining characters at the end.
- 1 ≤ word1.length, word2.length ≤ 100
- word1 and word2 consist of lowercase English letters.
Example
word1 = "abc", word2 = "pqr""apbqcr"The algorithm alternates characters from each string: 'a' from word1, 'p' from word2, 'b' from word1, 'q' from word2, 'c' from word1, and 'r' from word2. Since both strings are equal length, the merged string is simply the interleaving of characters.
Approach
Straightforward Solution
A brute-force approach would iterate over the maximum length of the two strings and append characters from each string if the index is valid. This approach is simple but requires careful boundary checks to avoid index errors.
Core Observation
The problem requires combining two sequences character-by-character in an alternating fashion, continuing until one sequence is exhausted, then appending the remainder of the other sequence.
Path to Optimal
The key insight is to use two pointers to track positions in each string and append characters alternately while both pointers are within bounds. After one string is exhausted, append the remaining characters from the other string. This approach is straightforward and optimal for the problem constraints.
Optimal Approach
Use two pointers i and j initialized to zero. While both pointers are within their respective string lengths, append characters from word1[i] and word2[j], then increment both pointers. After this loop, append any remaining characters from word1 or word2. Finally, join the accumulated characters into a single string and return it.
Time
O(n + m)
Each character from both strings is visited exactly once during the merge and append operations, where n and m are the lengths of word1 and word2 respectively.
Space
O(n + m)
The output string requires space proportional to the sum of the input strings' lengths, which is unavoidable. The auxiliary space used for the result list is also O(n + m).
Pattern Spotlight
Simulation (Two-Pointer Alternating Merge)
When merging two sequences alternately, use two pointers to track positions and append characters while both pointers are valid, then append the remainder of the longer sequence to complete the merge.
Solution
| 1 | class Solution: |
| 2 | def mergeAlternately(self, word1: str, word2: str) -> str: |
| 3 | i = j = 0 |
| 4 | res = [] |
| 5 | |
| 6 | while i < len(word1) and j < len(word2): |
| 7 | res.append(word1[i]) |
| 8 | res.append(word2[j]) |
| 9 | i += 1 |
| 10 | j += 1 |
| 11 | |
| 12 | while i < len(word1): |
| 13 | res.append(word1[i]) |
| 14 | i += 1 |
| 15 | |
| 16 | while j < len(word2): |
| 17 | res.append(word2[j]) |
| 18 | j += 1 |
| 19 | |
| 20 | return "".join(res) |
Step-by-Step Solution
Initialize Pointers and Result Container for Alternating Merge
| 3 | i = j = 0 |
| 4 | res = [] |
Objective
To set up two pointers for traversing each input string and a list to accumulate merged characters.
Key Insight
Using two pointers initialized to zero allows simultaneous traversal of both strings. A list is used to efficiently accumulate characters because string concatenation in Python is costly. This setup prepares for a clean, linear-time merge.
Interview Quick-Check
Core Logic
Two pointers track current indices in word1 and word2, enabling synchronized traversal.
Common Pitfalls & Bugs
Using string concatenation inside loops can lead to O(n²) time complexity; using a list and joining at the end is more efficient.
Merge Characters Alternately While Both Strings Have Remaining Characters
| 6 | while i < len(word1) and j < len(word2): |
| 7 | res.append(word1[i]) |
| 8 | res.append(word2[j]) |
| 9 | i += 1 |
| 10 | j += 1 |
Objective
To append characters from both strings alternately while both pointers are within their string lengths.
Key Insight
The loop condition ensures that characters are appended only when both strings have characters left to merge. Appending one character from each string per iteration maintains the alternating pattern. Incrementing both pointers advances the traversal synchronously.
Interview Quick-Check
Core Logic
The while loop merges characters alternately by appending from word1 and word2 and advancing both pointers.
State & Boundaries
The loop condition `i < len(word1) and j < len(word2)` ensures no index out-of-bounds errors.
Common Pitfalls & Bugs
Failing to increment both pointers correctly can cause infinite loops or incorrect merges.
Append Remaining Characters from the Longer String After Alternating Merge
| 12 | while i < len(word1): |
| 13 | res.append(word1[i]) |
| 14 | i += 1 |
| 16 | while j < len(word2): |
| 17 | res.append(word2[j]) |
| 18 | j += 1 |
Objective
To append any leftover characters from either word1 or word2 after the alternating merge loop completes.
Key Insight
Once one string is exhausted, the other may still have characters remaining. Two separate while loops handle these cases independently, appending all remaining characters to the result. This ensures the final merged string contains all characters from both inputs in the correct order.
Interview Quick-Check
Core Logic
Separate loops append remaining characters from word1 or word2 after the main alternating merge.
State & Boundaries
Each loop runs only if its pointer has not reached the end of its string.
Common Pitfalls & Bugs
Omitting these loops would result in missing characters from the longer string.
Join Accumulated Characters into Final Merged String
| 20 | return "".join(res) |
Objective
To convert the list of merged characters into a single string for the final output.
Key Insight
Joining a list of characters into a string is efficient and produces the desired output format. This step finalizes the result after all characters have been merged and appended.
Interview Quick-Check
Core Logic
Using `''.join(res)` efficiently concatenates all characters into the final string.
Common Pitfalls & Bugs
Returning the list directly or concatenating strings repeatedly would be incorrect or inefficient.
Line Analysis
This solution has 1 Critical line interviewers watch for.
return "".join(res)Join all characters in the result list into a single string and return it.
Joining the list into a string produces the final merged output efficiently, completing the algorithm.
res.append(word1[i])Append the current character from word1 to the result list.
Appending word1[i] maintains the alternating pattern by adding the next character from word1.
res.append(word2[j])Append the current character from word2 to the result list.
Appending word2[j] complements the previous append, preserving the alternating merge sequence.
res = []Initialize an empty list to accumulate merged characters.
Using a list for accumulation is efficient because string concatenation in Python is O(n) per operation; appending to a list is O(1) amortized, allowing linear-time merging.
while i < len(word1) and j < len(word2):Begin a loop that continues while both pointers are within their string lengths.
The loop condition ensures safe access to characters in both strings and maintains the alternating merge pattern until one string is exhausted.
while i < len(word1):Begin a loop to append remaining characters from word1 if any remain.
This loop handles the case where word1 is longer, ensuring no characters are omitted after the alternating merge.
res.append(word1[i])Append the current character from word1 to the result list.
Appending leftover characters preserves the order and completeness of the merged string.
while j < len(word2):Begin a loop to append remaining characters from word2 if any remain.
This loop handles the case where word2 is longer, ensuring no characters are omitted after the alternating merge.
res.append(word2[j])Append the current character from word2 to the result list.
Appending leftover characters preserves the order and completeness of the merged string.
i = j = 0Initialize pointers i and j to zero for traversing word1 and word2 respectively.
Starting both pointers at zero sets up synchronized traversal of both strings from their beginnings, enabling the alternating merge.
i += 1Increment pointer i to move to the next character in word1.
Advancing i ensures the next iteration accesses the subsequent character in word1, progressing the merge.
j += 1Increment pointer j to move to the next character in word2.
Advancing j ensures the next iteration accesses the subsequent character in word2, progressing the merge.
i += 1Increment pointer i to move to the next character in word1.
Advancing i ensures all remaining characters are processed sequentially.
j += 1Increment pointer j to move to the next character in word2.
Advancing j ensures all remaining characters are processed sequentially.
Test Your Understanding
Why is it necessary to handle the remaining characters of the longer string after the alternating merge loop?
Because the alternating merge only processes characters while both strings have remaining characters; once one string is exhausted, the other may still have characters left that must be appended to preserve all input data in the output.
Related Problems
Two Pointers pattern
Don't just read it. Drill it.
Reconstruct Merge Strings Alternately from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Merge Strings Alternately drill