Merge Strings Alternately - LeetCode 1768 Solution

Problem Overview

#

The Merge Strings Alternately problem from LeetCode asks you to merge two strings by adding letters in alternating order.

Problem Statement: 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.

Example:

• Input: word1 = "abc", word2 = "pqr"

• Output: "apbqcr"

• Input: word1 = "ab", word2 = "pqrs"

• Output: "apbqrs"

• Input: word1 = "abcd", word2 = "pq"

• Output: "apbqcd"

Solution Approach

#

C# Solution - Two Pointer with StringBuilder

#

Use a StringBuilder for efficient string building. Get the lengths of both strings and find the maximum length to determine how many iterations are needed. In each iteration, check if the current index is within bounds for each string, and if so, append the character from that string. This automatically handles strings of different lengths.

public class Solution {
    public string MergeAlternately(string word1, string word2) {
        var merged = new StringBuilder();

        var len1 = word1.Length;
        var len2 = word2.Length;

        var maxLen = Math.Max(len1, len2);

        for(int i = 0; i < maxLen; i++) {
            if( i < len1) merged.Append(word1[i]);
            if( i < len2) merged.Append(word2[i]);
        }

        return merged.ToString();
    }
}

Time Complexity: O(n + m) - where n and m are lengths of the two strings Space Complexity: O(n + m) - for the merged result string

Key Insights

#

1. StringBuilder Efficiency: Use StringBuilder instead of string concatenation for O(1) append operations
2. Maximum Length: Use Math.Max() to determine total iterations needed for both strings
3. Bounds Checking: Check each index against respective string lengths before appending
4. Alternating Pattern: Append from both strings in each iteration to achieve alternating order
5. Automatic Remainder: Longer string’s remaining characters are naturally appended after shorter string is exhausted
6. Single Loop: One loop with dual appends eliminates need for separate remainder handling

Related Problems

#

• Merge Sorted Array
• Zip Pairs of Lists
• Interleaving String

Video Tutorial

#

Watch the complete explanation and walkthrough in the video above for a detailed solution approach and implementation details.