Merge Strings Alternately

Problem Statement

The task requires merging two given input strings, word1 and word2, in an alternating pattern, starting with the first letter of word1. The resultant string combines characters from the two strings one by one until one of the strings runs out of characters. If any characters remain in either string after this interleaving, these additional characters are appended directly to the end of the resulting string. Your function must construct and return this merged string following the described pattern.

Examples

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

Example 3

Input:

word1 = "abcd", word2 = "pq"

Output:

"apbqcd"

Explanation:

 Notice that as word1 is longer, "cd" is appended to the end.
word1: a b c d
word2: p q
merged: a p b q c d

Constraints

• 1 <= word1.length, word2.length <= 100
• word1 and word2 consist of lowercase English letters.

Approach and Intuition

The goal is to generate a new string by alternating characters from word1 and word2, starting with word1. The process halts once we reach the end of one string and then appends any remaining characters from the other string. Here's a step-by-step breakdown of how to approach this:

1. Initialize an empty string result to store the merged characters.
2. Use a loop to iterate through the characters of word1 and word2. The looping continues until the index exceeds the length of at least one of the strings.
   • Append the current character from word1 to result.
   • Append the current character from word2 to result.
3. After exiting the loop, check if there are remaining characters in word1 or word2. Append those remaining characters to result.
4. Return the result string.

Considerations Based on Constraints:

• With a maximum possible string length of 100 for both strings, the solution needs to handle up to 200 iterations in the worst case, which is computationally feasible.
• The logic primarily hinges on correctly alternating characters and managing the addition of leftover characters from the longer string.
• Edge cases include scenarios where:
  • Both strings are of equal length.
  • One string is significantly longer than the other.
  • Exploring minimum length scenarios where one of the strings could just be a single character long.

By iterating through both strings simultaneously and handling the tail end remains, the described approach ensures that all characters are merged according to the rules and constraints given.

Solutions

class Solution {
public:
    string interleaveStrings(string str1, string str2) {
        int len1 = str1.length();
        int len2 = str2.length();
        string combined = "";
    
        for (int index = 0; index < max(len1, len2); index++) {
            if (index < len1) {
                combined.push_back(str1[index]);
            }
            if (index < len2) {
                combined.push_back(str2[index]);
            }
        }
    
        return combined;
    }
};