Merge Strings Alternately

How it works

Since we always process characters at the same index from both strings in each iteration, we can simplify to a single index variable. We iterate up to the length of the longer string, and for each index, we add the character from each string if that index is valid.

Steps

1. Let n and m be the lengths of word1 and word2.
2. Initialize an empty result list.
3. For each index i from 0 to max(n, m) - 1:
   • If i < n, append word1[i] to the result.
   • If i < m, append word2[i] to the result.
4. Return the joined result string.

Complexity

• Time complexity: O(n + m)
• Space complexity: O(n + m) for the output string.

Where n and m are the lengths of the strings word1 and word2 respectively.

Things to watch for

Forgetting to Append the Remaining Characters

When one string is longer than the other, the remaining characters must be appended after the alternating portion is complete. Stopping the loop when the shorter string ends without handling the leftover characters produces an incomplete result.

Using String Concatenation in a Loop

In many languages, repeatedly concatenating strings with + inside a loop creates a new string object each time, leading to O(n^2) time complexity. Use a StringBuilder, list of characters, or similar efficient structure to build the result, then join at the end.

class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        n, m = len(word1), len(word2)
        res = []
        for i in range(max(m, n)):
            if i < n:
                res.append(word1[i])
            if i < m:
                res.append(word2[i])
        return "".join(res)

class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        string res;
        for (int i = 0; i < n || i < m; i++) {
            if (i < n) {
                res += word1[i];
            }
            if (i < m) {
                res += word2[i];
            }
        }
        return res;
    }
};