Merge Strings Alternately - Leetcode Solution

Problem Link

💡 Step-by-Step Thought Process

Start with two input strings, for example: "abc" and "xyz".
Use a pointer for each string to keep track of where you are in the merging process.
Alternate characters between the two strings: take one from the first string, then one from the second.
Continue alternating until you reach the end of one or both strings.
If one string is longer than the other, append the remaining characters from that string to the result.
Return the final merged string.

Code Solution (Brute Force)

class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        characters = ""
        cur_word = 1
        a, b = 0, 0

        while a < len(word1) and b < len(word2):
            if cur_word == 1:
                characters += word1[a]
                a += 1
                cur_word = 2
            else:
                characters += word2[b]
                b += 1
                cur_word = 1
        
        while a < len(word1):
            characters += word1[a]
            a += 1
        
        while b < len(word2):
            characters += word2[b]
            b += 1
        
        return characters
        # Let A be the length of Word1
        # Let B be the length of Word2
        # Let T = A + B
        
        # Time: O(T^2)
        # Space: O(T)

#include <string>
using namespace std;

class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        string characters = "";
        int cur_word = 1;
        int a = 0, b = 0;
        int A = word1.size(), B = word2.size();

        while (a < A && b < B) {
            if (cur_word == 1) {
                characters += word1[a++];
                cur_word = 2;
            } else {
                characters += word2[b++];
                cur_word = 1;
            }
        }

        while (a < A) {
            characters += word1[a++];
        }

        while (b < B) {
            characters += word2[b++];
        }

        return characters;
    }
};

public class Solution {
    public String mergeAlternately(String word1, String word2) {
        String characters = "";
        int cur_word = 1;
        int a = 0, b = 0;
        int A = word1.length(), B = word2.length();

        while (a < A && b < B) {
            if (cur_word == 1) {
                characters += word1.charAt(a++);
                cur_word = 2;
            } else {
                characters += word2.charAt(b++);
                cur_word = 1;
            }
        }

        while (a < A) {
            characters += word1.charAt(a++);
        }

        while (b < B) {
            characters += word2.charAt(b++);
        }

        return characters;
    }
}

var mergeAlternately = function(word1, word2) {
    let A = word1.length, B = word2.length;
    let a = 0, b = 0;
    let result = '';

    while (a < A && b < B) {
        result += word1[a++];
        result += word2[b++];
    }

    while (a < A) {
        result += word1[a++];
    }

    while (b < B) {
        result += word2[b++];
    }

    return result;
};

String concatenation has linear time complexity, but appending to a list takes constant time. Using lists instead of strings enables a more efficient solution with O(n) time complexity.

Code Solution (Optimal)

class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        A, B = len(word1), len(word2)
        a, b = 0, 0
        s = []

        word = 1
        while a < A and b < B:
            if word == 1:
                s.append(word1[a])
                a += 1
                word = 2
            else:
                s.append(word2[b])
                b += 1
                word = 1
        
        while a < A:
            s.append(word1[a])
            a += 1
        
        while b < B:
            s.append(word2[b])
            b += 1
        
        return ''.join(s)
        # Let A be the length of Word1
        # Let B be the length of Word2
        # Let T = A + B
        
        # Time: O(T)
        # Space: O(T)

#include <string>
using namespace std;

class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        int A = word1.size(), B = word2.size();
        int a = 0, b = 0;
        string s;

        int word = 1;
        while (a < A && b < B) {
            if (word == 1) {
                s.push_back(word1[a++]);
                word = 2;
            } else {
                s.push_back(word2[b++]);
                word = 1;
            }
        }

        while (a < A) {
            s.push_back(word1[a++]);
        }

        while (b < B) {
            s.push_back(word2[b++]);
        }

        return s;
    }
};

public class Solution {
    public String mergeAlternately(String word1, String word2) {
        int A = word1.length(), B = word2.length();
        int a = 0, b = 0;
        StringBuilder s = new StringBuilder();

        int word = 1;
        while (a < A && b < B) {
            if (word == 1) {
                s.append(word1.charAt(a++));
                word = 2;
            } else {
                s.append(word2.charAt(b++));
                word = 1;
            }
        }

        while (a < A) {
            s.append(word1.charAt(a++));
        }

        while (b < B) {
            s.append(word2.charAt(b++));
        }

        return s.toString();
    }
}

var mergeAlternately = function(word1, word2) {
    const A = word1.length, B = word2.length;
    let a = 0, b = 0;
    const s = [];

    let word = 1;
    while (a < A && b < B) {
        if (word === 1) {
            s.push(word1[a++]);
            word = 2;
        } else {
            s.push(word2[b++]);
            word = 1;
        }
    }

    while (a < A) {
        s.push(word1[a++]);
    }

    while (b < B) {
        s.push(word2[b++]);
    }

    return s.join('');
};

Detailed Explanation

How to Merge Two Strings Alternately

The merge-strings-alternately problem asks you to combine two input strings by alternating their characters. Specifically, you take the first character of the first string, then the first character of the second string, then the second character of the first string, and so on — continuing until all characters from both strings have been added. If one string is longer than the other, the remaining characters are added at the end of the merged result.

For example, if the input strings are word1 = "abc" and word2 = "pqr", the merged string is "apbqcr". Each letter from word1 and word2 is taken one at a time, alternating between the two:

  word1:   a   b   c
  word2:   p   q   r
  result:  a + p + b + q + c + r → "apbqcr"

If the input strings have unequal lengths, the algorithm still works. Consider word1 = "ab" and word2 = "pqrs". The merging process goes:

  word1:   a   b
  word2:   p   q   r   s
  result:  a + p + b + q + r + s → "apbqrs"

Approach for Solving

To solve the merge-strings-alternately problem, use a loop that iterates through both strings at the same time. You use two pointers (or indices): one for each string. On each iteration:

If the current index is within the bounds of word1, add its character to the result.
If the current index is within the bounds of word2, add its character to the result.
Advance the index and repeat until both strings are fully processed.

Pseudocode

result = ""
i = 0
while i < max(length of word1, length of word2):
    if i < length of word1:
        result += word1[i]
    if i < length of word2:
        result += word2[i]
    i += 1
return result

Time and Space Complexity

Time Complexity: O(n + m), where n is the length of word1 and m is the length of word2.
Space Complexity: O(n + m) to store the final merged string.

Summary

The merge two strings alternately technique is a basic string manipulation task that can be solved using a simple loop and two indices. It is a good exercise for understanding character-by-character traversal and handling of unequal-length strings. The solution is efficient, easy to implement, and useful for anyone learning to work with string inputs in coding challenges.

Get Personalized Support at AlgoMap Bootcamp 💡