1768. Merge Strings Alternately - Explanation

Problem Link

Description

You are given two strings, word1 and word2. Construct a new string by merging them in alternating order, starting with word1 — take one character from word1, then one from word2, and repeat this process.

If one string is longer than the other, append the remaining characters from the longer string to the end of the merged result.

Return the final merged string.

Example 1:

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

Output: "axbycz"

Example 2:

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

Output: "aabbbxxc"

Constraints:

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

Company Tags

Please upgrade to NeetCode Pro to view company tags.



1. Two Pointers - I

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

Time & Space Complexity

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

Where nn and mm are the lengths of the strings word1word1 and word2word2 respectively.

2. Two Pointers - II

class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        n, m = len(word1), len(word2)
        res = []
        i = j = 0
        while i < n or j < m:
            if i < n:
                res.append(word1[i])
            if j < m:
                res.append(word2[j])
            i += 1
            j += 1
        return "".join(res)

Time & Space Complexity

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

Where nn and mm are the lengths of the strings word1word1 and word2word2 respectively.

3. One Pointer

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)

Time & Space Complexity

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

Where nn and mm are the lengths of the strings word1word1 and word2word2 respectively.