LeetCode 1768 - Merge Strings Alternately

LeetCode Problem 1768

Difficulty: 🟢 Easy
Topics: Two Pointers, String

Solution

Problem Understanding

The problem requires merging two input strings word1 and word2 in an alternating fashion, starting with the first character of word1. This means we take one character from word1, then one character from word2, and repeat this process until one or both strings are exhausted. If one string is longer than the other, the remaining characters from the longer string should be appended to the end of the merged result.

The input strings are guaranteed to contain only lowercase English letters, and their lengths range from 1 to 100. This ensures that we do not need to handle empty strings and that performance constraints are modest, so a straightforward linear-time solution will be sufficient. Important edge cases include situations where one string is significantly longer than the other or where both strings are of equal length.

The output is a single string representing the merged result according to the described alternating pattern. This means that the algorithm must handle uneven lengths correctly and maintain the order of characters from each original string.

Approaches

The brute-force approach would be to repeatedly remove the first character from each string and append it to the result until both strings are empty. While this produces the correct result, it is inefficient in languages like Python where string concatenation in a loop creates a new string at every step. The time complexity can degrade to O(n^2) in that case.

The optimal approach leverages two pointers or index counters to traverse both strings simultaneously. At each step, the character from word1 and then the character from word2 is appended to a result list. Once one string is exhausted, the remainder of the other string is appended in one operation. This maintains linear time complexity and avoids repeated string copying.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n*m)	O(n+m)	Repeated string concatenation at each step, inefficient in Python
Optimal	O(n + m)	O(n + m)	Use two pointers and a list to collect characters, then join

Algorithm Walkthrough

1. Initialize an empty list merged to store characters as we traverse both strings.
2. Initialize two pointers, i and j, starting at 0, to iterate over word1 and word2 respectively.
3. While both pointers are within the bounds of their respective strings:

• Append word1[i] to merged and increment i.
• Append word2[j] to merged and increment j.

4. After one string is exhausted, append the remaining substring from the other string directly to merged. This handles the case where the strings are of unequal length.
5. Convert the merged list to a string using ''.join(merged) and return it.

Why it works: The algorithm ensures that characters from both strings are added in alternating order until one string runs out. The invariant is that at every step, characters from both strings up to the current pointers are included in order. Any leftover characters are appended at the end, guaranteeing correctness.

Python Solution

class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        merged = []
        i, j = 0, 0
        while i < len(word1) and j < len(word2):
            merged.append(word1[i])
            i += 1
            merged.append(word2[j])
            j += 1
        # Append the remaining part of the longer string
        if i < len(word1):
            merged.append(word1[i:])
        if j < len(word2):
            merged.append(word2[j:])
        return ''.join(merged)

The implementation follows the algorithm closely. A list is used for efficiency instead of repeated string concatenation. Pointers i and j track progress through word1 and word2. The final join operation converts the list of characters into the required output string.

Go Solution

func mergeAlternately(word1 string, word2 string) string {
    var merged []byte
    i, j := 0, 0
    for i < len(word1) && j < len(word2) {
        merged = append(merged, word1[i])
        i++
        merged = append(merged, word2[j])
        j++
    }
    // Append remaining substring if any
    if i < len(word1) {
        merged = append(merged, word1[i:]...)
    }
    if j < len(word2) {
        merged = append(merged, word2[j:]...)
    }
    return string(merged)
}

In Go, we use a []byte slice to efficiently build the merged string. The logic mirrors the Python implementation. Go’s slice appending allows us to handle the remaining characters succinctly using ....

Worked Examples

Example 1: word1 = "abc", word2 = "pqr"

i	j	merged
0	0	a
1	0	ap
1	1	apb
2	1	apbq
2	2	apbqc
3	2	apbqcr

Example 2: word1 = "ab", word2 = "pqrs"

i	j	merged
0	0	a
1	0	ap
1	1	apb
2	1	apbq
2	2	apbqrs

Example 3: word1 = "abcd", word2 = "pq"

i	j	merged
0	0	a
1	0	ap
1	1	apb
2	1	apbq
2	2	apbqcd

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	We iterate through both strings once.
Space	O(n + m)	The merged string stores all characters from both inputs.

The complexity is linear in the combined length of the strings. Using a list or slice to build the result ensures appending is efficient.

Test Cases

# provided examples
assert Solution().mergeAlternately("abc", "pqr") == "apbqcr"  # equal length
assert Solution().mergeAlternately("ab", "pqrs") == "apbqrs"  # word2 longer
assert Solution().mergeAlternately("abcd", "pq") == "apbqcd"  # word1 longer

# edge cases
assert Solution().mergeAlternately("a", "b") == "ab"  # minimal length strings
assert Solution().mergeAlternately("x", "yz") == "xyz"  # first shorter
assert Solution().mergeAlternately("mn", "o") == "mon"  # second shorter
assert Solution().mergeAlternately("abc", "") == "abc"  # second empty handled (not needed but safe)
assert Solution().mergeAlternately("", "xyz") == "xyz"  # first empty handled (not needed but safe)

Test	Why
"abc", "pqr"	Equal length strings
"ab", "pqrs"	Second string longer
"abcd", "pq"	First string longer
"a", "b"	Minimal valid length
"x", "yz"	First string shorter than second
"mn", "o"	Second string shorter than first
"abc", ""	Second string empty (edge)
"", "xyz"	First string empty (edge)

Edge Cases

One important edge case is when one string is longer than the other. This could trip up a naive implementation that assumes equal length strings. The solution handles this by appending the remaining substring after the main loop.

Another edge case is strings of length 1. Some implementations might fail if they rely on loops assuming more than one character. The current approach correctly iterates even when length is 1.

Finally, handling strings where one of them is empty is another potential source of bugs, though the constraints guarantee at least one character in each string. By appending the remaining part of each string after the alternating loop, this scenario would still work correctly if the constraint were relaxed.