Merge Strings Alternately

Difficulty: Easy | Acceptance: 82.10% | Paid: No Topics: Two Pointers, String

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.

• Examples
• Constraints
• Two Pointers
• Single Loop with Min Length

Examples

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 <= 100
word1 and word2 consist of only lowercase English letters.

Two Pointers

Intuition We can use two pointers to traverse both strings simultaneously. We add characters from each string to the result one by one until one of the strings is fully traversed. Then, we append the remaining characters from the longer string.

Steps

• Initialize an empty result list/string and two pointers i and j to 0.
• Loop while i is within the bounds of word1 and j is within the bounds of word2.
• In each iteration, append word1[i] and word2[j] to the result, then increment both pointers.
• After the loop, one of the strings might still have characters left. Append the remaining substring of word1 starting from i and the remaining substring of word2 starting from j.
• Return the final merged string.

class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        res = []
        i = j = 0
        while i < len(word1) and j < len(word2):
            res.append(word1[i])
            res.append(word2[j])
            i += 1
            j += 1
        
        # Append remaining characters
        res.append(word1[i:])
        res.append(word2[j:])
        
        return "".join(res)

Complexity

• Time: O(n + m), where n and m are the lengths of word1 and word2. We iterate through both strings once.
• Space: O(n + m) to store the result string.
• Notes: This is the most efficient approach in terms of time complexity and is very readable.

Single Loop with Min Length

Intuition We can iterate up to the length of the shorter string to handle the alternating part safely. After the loop, we simply concatenate the remaining suffix of the longer string to the result.

Steps

• Determine the minimum length minLen between word1 and word2.
• Initialize an empty result list/string.
• Loop from index 0 to minLen - 1. In each iteration, append word1[i] followed by word2[i].
• After the loop, append the substring of word1 starting from minLen and the substring of word2 starting from minLen. One of these will be empty.
• Return the final merged string.

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

Complexity

• Time: O(n + m), where n and m are the lengths of word1 and word2.
• Space: O(n + m) to store the result string.
• Notes: This approach is functionally similar to the Two Pointers approach but might be slightly cleaner to read as it separates the alternating logic from the append logic.