Skip to main content
CodePeetCodePeet
CodePeet 250

Merge Strings Alternately

EASYProblemSolveExternal Links

Description

You are given two strings word1 and word2. Your task is to merge them into a single string by adding their characters in an alternating pattern, beginning with the first character of word1.

Take one character from word1, then one from word2, then one from word1, and so on. If one string is longer than the other, simply append all the remaining characters of the longer string to the end of the merged result.

Return the resulting merged string.

Examples

Example 1

Input: word1 = "abc", word2 = "pqr"

Output: "apbqcr"

Explanation: Both strings have the same length (3). We alternate perfectly: take 'a' from word1, then 'p' from word2, then 'b' from word1, then 'q' from word2, then 'c' from word1, then 'r' from word2. The merged result is "apbqcr".

Example 2

Input: word1 = "ab", word2 = "pqrs"

Output: "apbqrs"

Explanation: We alternate characters while both strings have them: 'a', 'p', 'b', 'q'. Now word1 is exhausted but word2 still has 'r' and 's' remaining. We append them to the end, giving "apbqrs".

Example 3

Input: word1 = "abcd", word2 = "pq"

Output: "apbqcd"

Explanation: We alternate: 'a', 'p', 'b', 'q'. Now word2 is exhausted but word1 still has 'c' and 'd' left. We append them, giving "apbqcd".

Constraints

  • 1 ≤ word1.length, word2.length ≤ 100
  • word1 and word2 consist of lowercase English letters

Editorial

Brute Force

Intuition

The most straightforward approach is to use a single index and iterate up to the length of the longer string. At each index position, we check: does word1 have a character at this index? If so, add it. Does word2 have a character at this index? If so, add it.

Think of it like two friends reading out letters from their name tags. They take turns — Friend 1 says a letter, then Friend 2 says a letter. When one friend runs out of letters, the other just finishes reading the rest of theirs.

We use repeated string concatenation to build the result character by character. While simple, this involves creating a new string object on every append operation.

Step-by-Step Explanation

Let's trace through with word1 = "ab", word2 = "pqrs":

Step 1: Initialize result = "". The longer string has length 4, so we iterate i from 0 to 3.

Step 2: i = 0. word1[0] = 'a' exists → append 'a'. word2[0] = 'p' exists → append 'p'. result = "ap".

Step 3: i = 1. word1[1] = 'b' exists → append 'b'. word2[1] = 'q' exists → append 'q'. result = "apbq".

Step 4: i = 2. word1[2] does not exist (word1 only has 2 characters) → skip. word2[2] = 'r' exists → append 'r'. result = "apbqr".

Step 5: i = 3. word1[3] does not exist → skip. word2[3] = 's' exists → append 's'. result = "apbqrs".

Step 6: Loop ends. Return "apbqrs".

Brute Force — Index-Based Alternating Merge — Watch how a single index walks through both strings simultaneously, picking characters from each when available and skipping when one string is exhausted.

Algorithm

  1. Calculate max_len = max(len(word1), len(word2)).
  2. Initialize an empty result string.
  3. For each index i from 0 to max_len - 1:
    a. If i < len(word1), append word1[i] to result.
    b. If i < len(word2), append word2[i] to result.
  4. Return the result string.

Code

class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        string result = "";
        int maxLen = max(word1.size(), word2.size());
        for (int i = 0; i < maxLen; i++) {
            if (i < word1.size()) {
                result += word1[i];
            }
            if (i < word2.size()) {
                result += word2[i];
            }
        }
        return result;
    }
};
class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        result = ""
        max_len = max(len(word1), len(word2))
        for i in range(max_len):
            if i < len(word1):
                result += word1[i]
            if i < len(word2):
                result += word2[i]
        return result
class Solution {
    public String mergeAlternately(String word1, String word2) {
        StringBuilder result = new StringBuilder();
        int maxLen = Math.max(word1.length(), word2.length());
        for (int i = 0; i < maxLen; i++) {
            if (i < word1.length()) {
                result.append(word1.charAt(i));
            }
            if (i < word2.length()) {
                result.append(word2.charAt(i));
            }
        }
        return result.toString();
    }
}

Complexity Analysis

Time Complexity: O(m + n)

Where m and n are the lengths of word1 and word2 respectively. We iterate max(m, n) times, and in each iteration we perform at most two constant-time character appends. Every character from both strings is processed exactly once.

However, in languages like Python and Java (without StringBuilder), string concatenation with += creates a new string each time, leading to O((m+n)²) total copy work in the worst case. The Java version above uses StringBuilder to avoid this pitfall.

Space Complexity: O(m + n)

The result string stores all characters from both input strings, so it uses O(m + n) space.

Why This Approach Is Not Efficient

The brute force approach works correctly and is already O(m + n) in time when using a list/StringBuilder for accumulation. However, it has a subtle inefficiency: the manual index management with boundary checks (if i < len(word1)) at every iteration is error-prone and verbose. We are manually handling the case where strings have different lengths using conditional logic.

For this particular problem, the brute force is already asymptotically optimal since we must read every character at least once, giving a lower bound of Ω(m + n). The "optimal" approach below does not improve time complexity but offers a cleaner, more idiomatic solution using a two-pointer technique that handles the two phases (alternating and appending remainder) more explicitly and elegantly, reducing the chance of bugs.

Optimal Approach - Two Pointers

Intuition

Instead of using a single shared index with boundary checks, we can use two independent pointers — one for each string. We process the merge in two clear phases:

Phase 1 — Alternating: While both pointers are within their respective strings, take one character from word1 (advance pointer 1) and one from word2 (advance pointer 2). This naturally handles the alternating pattern.

Phase 2 — Remainder: Once one pointer reaches the end of its string, append all remaining characters from the other string. Only one of these two "remainder" loops will execute.

Think of two conveyor belts feeding items onto a single output belt. While both belts are running, you alternate: take from belt 1, take from belt 2. When one belt runs out, the other just dumps everything remaining.

This approach is cleaner because the logic is split into distinct phases rather than mixing alternation and boundary-checking in a single loop. We also use a list (or StringBuilder) to collect characters and join them at the end, avoiding the O(n²) string concatenation trap.

Step-by-Step Explanation

Let's trace through with word1 = "ab", word2 = "pqrs":

Step 1: Initialize two pointers: i = 0 (for word1), j = 0 (for word2). Result list is empty.

Step 2: Phase 1 — Both pointers valid. Take word1[0] = 'a', advance i to 1. Take word2[0] = 'p', advance j to 1. Result: ['a', 'p'].

Step 3: Both pointers still valid. Take word1[1] = 'b', advance i to 2. Take word2[1] = 'q', advance j to 2. Result: ['a', 'p', 'b', 'q'].

Step 4: i = 2 is past the end of word1 (length 2). Phase 1 ends. Enter Phase 2.

Step 5: Phase 2 — word2 has remaining characters. Append word2[2] = 'r', advance j to 3. Result: ['a', 'p', 'b', 'q', 'r'].

Step 6: Append word2[3] = 's', advance j to 4. Result: ['a', 'p', 'b', 'q', 'r', 's'].

Step 7: j = 4 is past the end of word2. Phase 2 ends. Join the list: "apbqrs".

Result: Return "apbqrs".

Two Pointers — Alternating Merge with Remainder Append — Watch two independent pointers walk through their respective strings. During Phase 1, characters alternate from both strings. In Phase 2, the remaining characters from the longer string are appended.

Algorithm

  1. Initialize two pointers: i = 0 for word1, j = 0 for word2.
  2. Create an empty list to collect result characters.
  3. Phase 1 — Alternating: While i < len(word1) AND j < len(word2):
    a. Append word1[i] to result, increment i.
    b. Append word2[j] to result, increment j.
  4. Phase 2a — Remainder of word1: While i < len(word1):
    a. Append word1[i], increment i.
  5. Phase 2b — Remainder of word2: While j < len(word2):
    a. Append word2[j], increment j.
  6. Join the list into a string and return it.

Code

class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        int i = 0, j = 0;
        string result;
        // Phase 1: alternate while both have characters
        while (i < word1.size() && j < word2.size()) {
            result += word1[i++];
            result += word2[j++];
        }
        // Phase 2: append remaining characters
        while (i < word1.size()) {
            result += word1[i++];
        }
        while (j < word2.size()) {
            result += word2[j++];
        }
        return result;
    }
};
class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        result = []
        i, j = 0, 0
        # Phase 1: alternate while both have characters
        while i < len(word1) and j < len(word2):
            result.append(word1[i])
            result.append(word2[j])
            i += 1
            j += 1
        # Phase 2: append remaining characters from whichever string is longer
        result.append(word1[i:])
        result.append(word2[j:])
        return ''.join(result)
class Solution {
    public String mergeAlternately(String word1, String word2) {
        StringBuilder result = new StringBuilder();
        int i = 0, j = 0;
        // Phase 1: alternate while both have characters
        while (i < word1.length() && j < word2.length()) {
            result.append(word1.charAt(i++));
            result.append(word2.charAt(j++));
        }
        // Phase 2: append remaining characters
        while (i < word1.length()) {
            result.append(word1.charAt(i++));
        }
        while (j < word2.length()) {
            result.append(word2.charAt(j++));
        }
        return result.toString();
    }
}

Complexity Analysis

Time Complexity: O(m + n)

Where m = len(word1) and n = len(word2). In Phase 1, we process min(m, n) characters from each string (2 × min(m, n) appends). In Phase 2, we process the remaining |m - n| characters. Total characters processed: m + n. Each append to a list or StringBuilder is O(1) amortized. The final join is O(m + n). So overall time is O(m + n).

Space Complexity: O(m + n)

The result stores all m + n characters. The list/StringBuilder used for accumulation requires O(m + n) space. No other data structures grow with input size. This is optimal since the output itself requires O(m + n) space — we cannot do better.