algoadvance

Leetcode 1768. Merge Strings Alternately

Problem Statement

1. Merge Strings Alternately

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 to 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 "apbqcr".

Example 2:

Input: word1 = "ab", word2 = "pqrs"
Output: "apbqrs"
Explanation: Notice that as word2 is longer, "rs" is appended to the end of the merged string.

Example 3:

Input: word1 = "abcd", word2 = "pq"
Output: "apbqcd"
Explanation: Notice that as word1 is longer, "cd" is appended to the end of the merged string.

Clarifying Questions

1. Are word1 and word2 always non-empty?
   • Yes, you can assume that both strings are non-empty.
2. What is the maximum length for word1 and word2?
   • You can assume the length of both strings does not exceed 100.

Strategy

1. Initialize an empty result string.
2. Use two indices to track positions in word1 and word2.
3. Iterate over the length of the shortest string, appending characters alternately.
4. After we’ve iterated through the shortest string, append the remaining substring of the longer string to the result.
5. Return the result string.

Code

#include <iostream>
#include <string>

std::string mergeAlternately(const std::string& word1, const std::string& word2) {
    std::string result;
    int i = 0, j = 0;
    int len1 = word1.size(), len2 = word2.size();
    
    // Merge the strings alternately
    while (i < len1 && j < len2) {
        result += word1[i++];
        result += word2[j++];
    }
    
    // If there are remaining characters in word1
    while (i < len1) {
        result += word1[i++];
    }
    
    // If there are remaining characters in word2
    while (j < len2) {
        result += word2[j++];
    }
    
    return result;
}

int main() {
    std::string word1 = "abc";
    std::string word2 = "pqr";
    std::cout << mergeAlternately(word1, word2) << std::endl;  // Output: apbqcr
    
    word1 = "ab";
    word2 = "pqrs";
    std::cout << mergeAlternately(word1, word2) << std::endl;  // Output: apbqrs
    
    word1 = "abcd";
    word2 = "pq";
    std::cout << mergeAlternately(word1, word2) << std::endl;  // Output: apbqcd
    
    return 0;
}

Time Complexity

• The time complexity of this solution is (O(n + m)), where n is the length of word1 and m is the length of word2. This is because we only need to iterate through both strings once.
• The space complexity is also (O(n + m)), as we are storing the result in a string that can potentially have a length of (n + m).

This approach ensures that the solution is efficient and straightforward to implement.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?