Leetcode 1768. Merge Strings Alternately

Problem

Leetcode 1768 - Merge Strings Alternately

Example:

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

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

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

Approach

We use 2 pointers to track each index. Meaning that we have pointer1 at word1 starting from 0 and pointer2 at word2 starting from 0.

We run while loop until one of them finishes iterating the word. Once this is over, we add the remainder of word that hasn’t been iterated.

Visualization of the Approach:

word1 = 'ab', word2 = 'pqrs'
p1 = 0, p2 = 0
res = ""

res = 'ap'
p1 = 1, p2 = 1

res = 'apbq'
p1 = 2, p2 = 2
Since, p1 == len(word1) we stop while loop

Add the remainder of word1, word2 in res
res = 'apbqrs'

Output: 'apbqrs'

Here is the Python code for the solution:

class Solution:
     def mergeAlternatively(self, word1: str, word2: str) -> str:
        p1, p2 = 0, 0
        res = ""

        while p1 < len(word1) and p2 < len(word2):
            res += word1[p1] + word2[p2]
            p1 += 1
            p2 += 1
        
        # add the remainder of words after loop
        res += word1[p1:]
        res += word2[p2:]
        return res

Time Complexity and Space Complexity

Time Complexity: $O(n+m)$ where $n$ is length of word1 and $m$ is length of word2

Space Complexity: $O(n+m)$ where $n$ is length of word1 and $m$ is length of word2