algoadvance

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.

Example 1:

Input: word1 = "abc", word2 = "pqr"
Output: "apbqcr"

Example 2:

Input: word1 = "ab", word2 = "pqrs"
Output: "apbqrs"

Example 3:

Input: word1 = "abcd", word2 = "pq"
Output: "apbqcd"

Clarifying Questions

  1. Can the input strings be empty?
  2. Are there any constraints on the length of the strings?
  3. Can we assume that both inputs are always valid strings?

Strategy

  1. Initialize an empty list to collect merged characters.
  2. Use a loop to iterate over the range of the maximum length of the two words, so that we can handle cases where one word is longer.
  3. Within each iteration, check if the current index exists in word1 and word2, and append the characters to the result list if they do.
  4. Convert the list of characters to a string and return it as the final merged string.

Code

def mergeAlternately(word1: str, word2: str) -> str:
    # Initialize an empty list to collect the merged characters
    merged = []
    
    # Get the length of both words
    len1, len2 = len(word1), len(word2)
    
    # Iterate through the maximum length of both words
    for i in range(max(len1, len2)):
        if i < len1:
            merged.append(word1[i])
        if i < len2:
            merged.append(word2[i])
    
    # Convert the list of characters to a string
    return ''.join(merged)

Time Complexity

The time complexity of this algorithm is O(n + m), where n is the length of word1 and m is the length of word2. This is because we are iterating through the strings only once, and all other operations (checking index existence, appending to the list) take constant time.

Test Cases

  1. mergeAlternately("abc", "pqr") should return "apbqcr"
  2. mergeAlternately("ab", "pqrs") should return "apbqrs"
  3. mergeAlternately("abcd", "pq") should return "apbqcd"
  4. mergeAlternately("", "pqrs") should return "pqrs"
  5. mergeAlternately("abcd", "") should return "abcd"

Try our interview co-pilot at AlgoAdvance.com