You are given two strings word1 and word2. Merge the strings by adding letters in alternating order, starting with word1. If a string is longer than the other, append the additional letters onto the end of the merged string.
Return the merged string.
Example 1:
Input: word1 = "abc", word2 = "pqr" Output: "apbqcr" Explanation: The merged string will be merged as so: word1: a b c word2: p q r merged: a p b q c r
Example 2:
Input: word1 = "ab", word2 = "pqrs" Output: "apbqrs" Explanation: Notice that as word2 is longer, "rs" is appended to the end. word1: a b word2: p q r s merged: a p b q r s
Example 3:
Input: word1 = "abcd", word2 = "pq" Output: "apbqcd" Explanation: Notice that as word1 is longer, "cd" is appended to the end. word1: a b c d word2: p q merged: a p b q c d
Constraints:
1 <= word1.length, word2.length <= 100word1 and word2 consist of lowercase English letters.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.
This approach uses a loop to iterate through the characters in the strings by index. We initiate a loop for the length of the shorter string, adding characters alternately from each string to a result. Once the loop ends, we append the remaining part of the longer string.
The function mergeAlternately initializes by determining the lengths of the input strings. It allocates memory for the result string that can accommodate both input strings' lengths combined. It uses two indices to add characters alternately from each input string. When one string ends, the remaining characters of the other string are appended to the result. Finally, the function returns the merged string.
Time Complexity: O(n + m), where n and m are the lengths of the two strings.
Space Complexity: O(n + m) for the resulting string.
This approach uses recursion to merge the strings by alternating characters. It utilizes recursive calls to handle the process of alternately taking characters from each string, ending the recursion once one of the strings is fully consumed. The remaining part of the longer string is then joined directly to the result.
This recursive function merge_alternately checks if either string is empty. If so, it returns the remaining part of the other string. Otherwise, it returns the first character of each string concatenated with a recursive call using the rest of the strings.
Python
Time Complexity: O(n + m), where n and m are the lengths of the two strings.
Space Complexity: O(n + m) for call stack and resulting string in the worst case.
We traverse the two strings word1 and word2, take out the characters one by one, and append them to the result string. The Python code can be simplified into one line.
The time complexity is O(m + n), where m and n are the lengths of the two strings respectively. Ignoring the space consumption of the answer, the space complexity is O(1).
| Approach | Complexity |
|---|---|
| Iterative Merge with Indices | Time Complexity: O(n + m), where n and m are the lengths of the two strings. |
| Recursive Approach | Time Complexity: O(n + m), where n and m are the lengths of the two strings. |
| Direct Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Merge with Indices | O(n + m) | O(1) | General case. Most efficient and interview‑preferred solution. |
| Recursive Approach | O(n + m) | O(n + m) | Useful for demonstrating recursion and problem decomposition. |
Merge Strings Alternately - Leetcode 1768 - Python • NeetCodeIO • 44,433 views views
Watch 9 more video solutions →Practice Merge Strings Alternately with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor