Hello, Welcome to my August Challenge of Problem Solving and finding solutions to Leetcode's Data Structures and Algorithm questions. Here, I choose a question daily and try to solve it, and finally pen down my process of flow in solving the question.

I hope you find it helpful. Today I will be solving Leetcode question 1768 - Merge Strings Alternately

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.

Return the merged string.

Example 1:

Input: word1 = "abc", word2 = "pqr"
Output: "apbqcr"
Explanation: The merged string will be merged as so:
word1:  a   b   c
word2:    p   q   r
merged: a p b q c r

Example 2:

Input: word1 = "ab", word2 = "pqrs"
Output: "apbqrs"
Explanation: Notice that as word2 is longer, "rs" is appended to the end.
word1:  a   b 
word2:    p   q   r   s
merged: a p b q   r   s

The Approach

This particular problem involves merging two strings by alternating the characters from each string. The simplest approach to solving it would be to use two pointers, one for each string, and iterate over the strings while appending the characters alternately to a new string. If one of the strings is longer than the other, we can simply append the remaining characters to the end of the new string.

The Brute Force Approach

The brute force approach to merge two strings word1 and word2 by adding letters in alternating order would involve a straightforward iteration through both strings and appending characters to the result string one by one.

class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
         merged = ""
         len1, len2 = len(word1), len(word2)
         max_len = max(len1, len2)

        for i in range(max_len):
        if i < len1:
            merged += word1[i]
        if i < len2:
            merged += word2[i]

    return merged

In this brute force approach, we initialize an empty string merged to store the merged result. We then calculate the lengths of both word1 and word2 and find the maximum length between the two.

Next, we use a for loop to iterate through the range from 0 to the maximum length. In each iteration, we check if the index i is less than the length of word1, and if so, we add the character at index i from word1 to the merged string. Similarly, we check if the index i is less than the length of word2, and if so, we add the character at index i from word2 to the merged string.

The loop ensures that characters from both strings are added in alternating order until one of the strings is fully processed. If one string is longer than the other, the loop will continue to add the remaining characters from the longer string to the end of the merged string.

Not an optimal solution

Time Complexity: O(max(len(word1), len(word2))), where n is the length of the longer string.

Space Complexity: O(len(word1) + len(word2)), where n is the length of the merged string.

The brute force approach requires extra space to store the merged result, which is proportional to the sum of the lengths of the input strings. This space usage is reasonable for most cases, especially when the input strings are not extremely large.

The Optimal Solution

An optimized solution for merging two strings by adding letters in alternating order is one that directly generates the merged string without using additional space for intermediate results. This approach reduces the space complexity to O(1) while maintaining the same time complexity as the brute force approach.

class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        len1, len2 = len(word1), len(word2)
        max_len = max(len1, len2)

        merged = ""
        for i in range(max_len):
            if i < len1:
                merged += word1[i]
            if i < len2:
                merged += word2[i]

        return merged

This optimized solution still maintains the same time complexity as the brute force approach, which is O(max(len(word1), len(word2))). However, it is more efficient in terms of space complexity, as it does not require additional memory proportional to the sum of the lengths of the input strings

Conclusion

The optimized solution for merging two strings by adding letters in alternating order is both time and space efficient. By directly generating the merged string without using an additional list or generator, the solution achieves a space complexity of O(1), which is optimal and minimizes memory usage, particularly for very large strings. The optimized solution strikes a balance between simplicity and efficiency.