Problem

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

Example 1

1
2
3
4
5
6

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

1
2
3
4
5
6

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

1
2
3
4
5
6

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 lowercase English letters.

Solution

Method 1 – Two Pointers

Intuition

To merge two strings alternately, use two pointers to pick characters from each string in turn. If one string is longer, append its remaining characters at the end.

Approach

  1. Initialize two pointers, one for each string.
  2. While either pointer is within its string:
    • If both pointers are valid, append one character from each string alternately.
    • If one string is exhausted, append the remaining characters from the other string.
  3. Return the merged string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        int i = 0, j = 0, n = word1.size(), m = word2.size();
        string ans;
        while (i < n || j < m) {
            if (i < n) ans += word1[i++];
            if (j < m) ans += word2[j++];
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func mergeAlternately(word1, word2 string) string {
    i, j := 0, 0
    n, m := len(word1), len(word2)
    ans := make([]byte, 0, n+m)
    for i < n || j < m {
        if i < n {
            ans = append(ans, word1[i])
            i++
        }
        if j < m {
            ans = append(ans, word2[j])
            j++
        }
    }
    return string(ans)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public String mergeAlternately(String word1, String word2) {
        int i = 0, j = 0, n = word1.length(), m = word2.length();
        StringBuilder ans = new StringBuilder();
        while (i < n || j < m) {
            if (i < n) ans.append(word1.charAt(i++));
            if (j < m) ans.append(word2.charAt(j++));
        }
        return ans.toString();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun mergeAlternately(word1: String, word2: String): String {
        var i = 0; var j = 0
        val n = word1.length; val m = word2.length
        val ans = StringBuilder()
        while (i < n || j < m) {
            if (i < n) ans.append(word1[i++])
            if (j < m) ans.append(word2[j++])
        }
        return ans.toString()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def merge_alternately(word1: str, word2: str) -> str:
    i, j = 0, 0
    n, m = len(word1), len(word2)
    ans = []
    while i < n or j < m:
        if i < n:
            ans.append(word1[i])
            i += 1
        if j < m:
            ans.append(word2[j])
            j += 1
    return ''.join(ans)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn merge_alternately(word1: String, word2: String) -> String {
        let (mut i, mut j) = (0, 0);
        let (n, m) = (word1.len(), word2.len());
        let mut ans = String::with_capacity(n + m);
        let w1 = word1.as_bytes();
        let w2 = word2.as_bytes();
        while i < n || j < m {
            if i < n {
                ans.push(w1[i] as char);
                i += 1;
            }
            if j < m {
                ans.push(w2[j] as char);
                j += 1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    mergeAlternately(word1: string, word2: string): string {
        let i = 0, j = 0, n = word1.length, m = word2.length;
        let ans = '';
        while (i < n || j < m) {
            if (i < n) ans += word1[i++];
            if (j < m) ans += word2[j++];
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n + m), where n and m are the lengths of the two strings.
  • 🧺 Space complexity: O(n + m), for the result string.