LeetCode Solutions Blog

Merge Strings Alternately

Number: 1894

Difficulty: Easy

Paid? No

Problem Description

Given two strings word1 and word2, merge them by alternating characters starting with word1. If one string is longer than the other, append the remaining characters to the end of the merged string.

Key Insights

Use two pointers to iterate through both strings.
Append characters alternately until one string is exhausted.
After the loop, append any remaining characters from the longer string.
Ensure an O(n + m) time complexity where n and m are the lengths of the two strings.

Space and Time Complexity

Time Complexity: O(n + m)
Space Complexity: O(n + m)

Solution

The solution involves initializing two pointers (or indices) for the two strings and iterating over them simultaneously. At each iteration, add the character from word1 followed by the character from word2. When one pointer reaches the end of its string, append the remainder of the other string to the result. This approach employs a straightforward two-pointer technique and string concatenation.

Code Solutions

# Define function to merge two strings alternately
def merge_alternately(word1: str, word2: str) -> str:
    # Initialize an empty list to collect merged characters
    merged = []
    # Determine the minimum length to iterate for both strings
    min_length = min(len(word1), len(word2))
    
    # Iterate over both strings up to the minimum length
    for i in range(min_length):
        # Append character from word1
        merged.append(word1[i])
        # Append character from word2
        merged.append(word2[i])
    
    # After the loop, append the remaining part of word1 if any
    if min_length < len(word1):
        merged.append(word1[min_length:])
    # Append the remaining part of word2 if any
    if min_length < len(word2):
        merged.append(word2[min_length:])
    
    # Join all parts into a final string and return
    return ''.join(merged)

# Example usage:
print(merge_alternately("abc", "pqr"))  # Output: "apbqcr"