Leetcode 1768: Merge Strings Alternately

Input: The input consists of two strings `word1` and `word2`, both containing lowercase English letters.

Example: word1 = 'cat', word2 = 'dog'

Constraints:

• 1 <= word1.length, word2.length <= 100

• word1 and word2 consist of lowercase English letters

Output: Return the merged string where the characters from `word1` and `word2` alternate. If one string is longer than the other, append the remaining characters from the longer string.

Example: Output: 'cadtog'

Constraints:

• The merged string must respect the alternating character pattern.

Goal: The goal is to merge two strings by alternating their characters, starting with the first character of `word1`, and append any remaining characters from the longer string at the end.

Steps:

• Initialize two pointers, one for each string.

• Alternate between adding characters from `word1` and `word2` to the result string.

• After one string is exhausted, append the remaining characters from the longer string.

Goal: The constraints specify the size limits for the input strings and the valid character set.

Steps:

• 1 <= word1.length, word2.length <= 100

• word1 and word2 consist of lowercase English letters

Assumptions:

• Both `word1` and `word2` are non-empty strings.

• Input: word1 = 'cat', word2 = 'dog'

• Explanation: The strings have the same length, so the merged string alternates the characters from both strings: 'c', 'a', 't', 'd', 'o', 'g'.

• Input: word1 = 'hello', word2 = 'worlds'

• Explanation: Here, `word2` is longer, so after alternating characters, the remaining 's' from `word2` is appended to the end of the merged string.

Approach: The problem can be solved by alternating between the characters of both strings while keeping track of the current position in each string. Once one string is exhausted, we append the remaining characters from the other string.

Observations:

• We need to alternate characters from both strings while ensuring that we handle cases where the strings have different lengths.

• By using two pointers (one for each string), we can easily alternate characters from both strings.

Steps:

• Initialize an empty result string.

• Use two pointers, one for `word1` and one for `word2`.

• Alternately add characters from both strings to the result string.

• Once one string is exhausted, append the remaining characters from the other string.

Empty Inputs:

• The input strings will not be empty, as per the problem constraints.

Large Inputs:

• The solution should work efficiently for strings of length up to 100.

Special Values:

• If both strings are of equal length, the merged string should alternate characters from both strings evenly.

Constraints:

• The strings will always contain lowercase English letters and will be at least 1 character long.

string mergeAlternately(string w1, string w2) {
    string res = "";
    int i = 0, j = 0;
    while(i < w1.size() || j < w2.size()) {
        if(i < w1.size()) {
            res += w1[i];
            i++;
        }
        if(j < w2.size()) {
            res += w2[j];
            j++;
        }
    }
    return res;
}

1 : Function Definition

string mergeAlternately(string w1, string w2) {

The function `mergeAlternately` is defined, which takes two strings, `w1` and `w2`, as input and will return the merged result.

2 : Variable Initialization

    string res = "";

A string variable `res` is initialized to store the merged result of the two strings.

3 : Variable Initialization

    int i = 0, j = 0;

Two integer variables `i` and `j` are initialized to keep track of the current index in strings `w1` and `w2`, respectively.

4 : Loop Initialization

    while(i < w1.size() || j < w2.size()) {

A while loop begins, running until both strings have been fully traversed. It continues as long as there are characters left in either `w1` or `w2`.

5 : Conditional Check

        if(i < w1.size()) {

This condition checks if there are remaining characters in string `w1` (i.e., `i` is less than the size of `w1`).

6 : String Manipulation

            res += w1[i];

If there are characters remaining in `w1`, the next character (`w1[i]`) is appended to `res`.

7 : Variable Update

            i++;

The index `i` is incremented to move to the next character in `w1`.

8 : Conditional Check

        if(j < w2.size()) {

This condition checks if there are remaining characters in string `w2` (i.e., `j` is less than the size of `w2`).

9 : String Manipulation

            res += w2[j];

If there are characters remaining in `w2`, the next character (`w2[j]`) is appended to `res`.

10 : Variable Update

            j++;

The index `j` is incremented to move to the next character in `w2`.

11 : Return Statement

    return res;

Return the merged string `res` as the result of the function.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The solution iterates through each character of both strings once.

Best Case: O(n)

Worst Case: O(n)

Description: We use additional space for the result string, which can have a length equal to the sum of the lengths of both input strings.

Leetcode 1768: Merge Strings Alternately

Explore →