Jobs

Interviews

Discussions

Merge Strings Alternately

Easy

Asked by:

More companies

64 views

Topics:

StringsTwo Pointers

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

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.

Try coding it in LeetCode

Merge Strings Alternately

Easy

Asked by:

64 views

Topics:

StringsTwo Pointers

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

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input strings, word1 and word2, be empty or null?
Are there any constraints on the length of the input strings?
Is the desired output a new string, or am I allowed to modify either of the input strings?
Are the input strings guaranteed to contain only alphanumeric characters, or might there be other characters?
If one string is significantly longer than the other, is there any preferred way to optimize appending the remaining characters?

Brute Force Solution

Approach

The goal is to weave two strings together, one character at a time. The brute force method simply builds the merged string character by character, taking turns from each original string until both are used up. If one string runs out of characters first, we append the rest of the other string.

Here's how the algorithm would work step-by-step:

Start with an empty combined string.
Take the first character from the first string and add it to the combined string.
Then take the first character from the second string and add it to the combined string.
Keep alternating between the strings, adding one character at a time to the combined string.
If you run out of characters in one string, just add the remaining characters from the other string to the combined string.
The combined string is now the merged string.

Code Implementation

def merge_strings_alternately(word1, word2):
    merged_string = ""
    word1_length = len(word1)
    word2_length = len(word2)
    index1 = 0
    index2 = 0

    # Iterate while both strings have characters.
    while index1 < word1_length and index2 < word2_length:

        # Add the next char from the first word.
        merged_string += word1[index1]
        index1 += 1

        # Add the next char from the second word.
        merged_string += word2[index2]
        index2 += 1

    # Append remaining characters, if any, from word1.
    if index1 < word1_length:

        # Add all remaining from the first word.
        merged_string += word1[index1:]

    # Append remaining characters, if any, from word2.
    if index2 < word2_length:

        # Add all remaining from the second word.
        merged_string += word2[index2:]

    return merged_string

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through both input strings (word1 and word2) at most once. In the worst case, the length of the longer string determines the number of iterations needed to merge the strings. Appending characters to the combined string happens in constant time for each character. Therefore, the time complexity is directly proportional to the combined length of the input strings, which is represented as O(n), where n is the total number of characters in both strings.

Space Complexity

O(N) – The algorithm constructs a new string to store the merged result. In the worst case, the length of the merged string will be the sum of the lengths of the two input strings. Therefore, the auxiliary space required grows linearly with the total length of the input strings, which we can denote as N. Thus, the space complexity is O(N).

Optimal Solution

Approach

The goal is to combine two strings by picking characters from each one in turn. We want to construct a new string by alternating characters until we run out of characters in one or both original strings. After one string is used up, we simply add the remaining part of the other string to the result.

Here's how the algorithm would work step-by-step:

Start with an empty combined string.
Take the first character from the first string and add it to the combined string.
Then, take the first character from the second string and add it to the combined string.
Keep alternating, grabbing one character at a time from each string and adding it to the combined string.
If you run out of characters in one of the strings, stop alternating.
If the first string still has characters left, add all of those remaining characters to the end of the combined string.
If the second string still has characters left, add all of those remaining characters to the end of the combined string.
The combined string is now complete.

Code Implementation

def merge_strings_alternately(word1, word2):
    merged_string = ""
    word1_length = len(word1)
    word2_length = len(word2)
    index1 = 0
    index2 = 0

    # Iterate while both strings have characters.
    while index1 < word1_length and index2 < word2_length:
        merged_string += word1[index1]
        index1 += 1
        merged_string += word2[index2]
        index2 += 1

    # Append any remaining characters from word1.
    if index1 < word1_length:
        # Add remaining characters from word1
        merged_string += word1[index1:]

    # Append any remaining characters from word2.
    if index2 < word2_length:
        # Add remaining characters from word2
        merged_string += word2[index2:]

    return merged_string

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through both input strings (word1 and word2) simultaneously using a single loop that runs at most min(len(word1), len(word2)) times. After the loop, it potentially appends the remaining characters from either word1 or word2. The length of the remaining portion of either string is at most max(len(word1), len(word2)). Therefore, the time complexity is bounded by the maximum length of the two input strings, which we can represent as n. Thus, the overall time complexity is O(n).

Space Complexity

O(N) – The algorithm constructs a new string to store the merged result. The size of this string can grow up to the combined length of the input strings. Therefore, the auxiliary space required is proportional to N, where N is the total number of characters in the merged string, which is the sum of the lengths of the two input strings. Hence, the space complexity is O(N).

Edge Cases

Case	How to Handle
word1 is null	Return word2 if word1 is null, or an empty string if both are null to avoid NullPointerException.
word2 is null	Return word1 if word2 is null, or an empty string if both are null to avoid NullPointerException.
Both word1 and word2 are empty strings	Return an empty string, representing the merged result of two empty inputs.
word1 is an empty string	Return word2, as there is nothing to merge from word1.
word2 is an empty string	Return word1, as there is nothing to merge from word2.
Very long strings for word1 and word2	The solution should use StringBuilder or similar to build the merged string efficiently to avoid quadratic time complexity associated with string concatenation.
word1 and word2 are of vastly different lengths	The algorithm correctly appends remaining characters of the longer string after alternating through the shorter string length, so difference in length is naturally handled.
Strings containing unicode/special characters	Ensure that the character-by-character concatenation or string building handles unicode/special characters correctly according to the programming language's string implementation (e.g., UTF-8 or UTF-16).

word1 is null

How to Handle:

Return word2 if word1 is null, or an empty string if both are null to avoid NullPointerException.

word2 is null

How to Handle:

Return word1 if word2 is null, or an empty string if both are null to avoid NullPointerException.

Both word1 and word2 are empty strings

How to Handle:

Return an empty string, representing the merged result of two empty inputs.

word1 is an empty string

How to Handle:

Return word2, as there is nothing to merge from word1.

word2 is an empty string

How to Handle:

Return word1, as there is nothing to merge from word2.

Very long strings for word1 and word2

How to Handle:

The solution should use StringBuilder or similar to build the merged string efficiently to avoid quadratic time complexity associated with string concatenation.

word1 and word2 are of vastly different lengths

How to Handle:

The algorithm correctly appends remaining characters of the longer string after alternating through the shorter string length, so difference in length is naturally handled.

Strings containing unicode/special characters

How to Handle:

Ensure that the character-by-character concatenation or string building handles unicode/special characters correctly according to the programming language's string implementation (e.g., UTF-8 or UTF-16).

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input strings, word1 and word2, be empty or null?
Are there any constraints on the length of the input strings?
Is the desired output a new string, or am I allowed to modify either of the input strings?
Are the input strings guaranteed to contain only alphanumeric characters, or might there be other characters?
If one string is significantly longer than the other, is there any preferred way to optimize appending the remaining characters?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with an empty combined string.
Take the first character from the first string and add it to the combined string.
Then take the first character from the second string and add it to the combined string.
Keep alternating between the strings, adding one character at a time to the combined string.
If you run out of characters in one string, just add the remaining characters from the other string to the combined string.
The combined string is now the merged string.

Code Implementation

def merge_strings_alternately(word1, word2):
    merged_string = ""
    word1_length = len(word1)
    word2_length = len(word2)
    index1 = 0
    index2 = 0

    # Iterate while both strings have characters.
    while index1 < word1_length and index2 < word2_length:

        # Add the next char from the first word.
        merged_string += word1[index1]
        index1 += 1

        # Add the next char from the second word.
        merged_string += word2[index2]
        index2 += 1

    # Append remaining characters, if any, from word1.
    if index1 < word1_length:

        # Add all remaining from the first word.
        merged_string += word1[index1:]

    # Append remaining characters, if any, from word2.
    if index2 < word2_length:

        # Add all remaining from the second word.
        merged_string += word2[index2:]

    return merged_string

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start with an empty combined string.
Take the first character from the first string and add it to the combined string.
Then, take the first character from the second string and add it to the combined string.
Keep alternating, grabbing one character at a time from each string and adding it to the combined string.
If you run out of characters in one of the strings, stop alternating.
If the first string still has characters left, add all of those remaining characters to the end of the combined string.
If the second string still has characters left, add all of those remaining characters to the end of the combined string.
The combined string is now complete.

Code Implementation

def merge_strings_alternately(word1, word2):
    merged_string = ""
    word1_length = len(word1)
    word2_length = len(word2)
    index1 = 0
    index2 = 0

    # Iterate while both strings have characters.
    while index1 < word1_length and index2 < word2_length:
        merged_string += word1[index1]
        index1 += 1
        merged_string += word2[index2]
        index2 += 1

    # Append any remaining characters from word1.
    if index1 < word1_length:
        # Add remaining characters from word1
        merged_string += word1[index1:]

    # Append any remaining characters from word2.
    if index2 < word2_length:
        # Add remaining characters from word2
        merged_string += word2[index2:]

    return merged_string

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
word1 is null	Return word2 if word1 is null, or an empty string if both are null to avoid NullPointerException.
word2 is null	Return word1 if word2 is null, or an empty string if both are null to avoid NullPointerException.
Both word1 and word2 are empty strings	Return an empty string, representing the merged result of two empty inputs.
word1 is an empty string	Return word2, as there is nothing to merge from word1.
word2 is an empty string	Return word1, as there is nothing to merge from word2.
Very long strings for word1 and word2	The solution should use StringBuilder or similar to build the merged string efficiently to avoid quadratic time complexity associated with string concatenation.
word1 and word2 are of vastly different lengths	The algorithm correctly appends remaining characters of the longer string after alternating through the shorter string length, so difference in length is naturally handled.
Strings containing unicode/special characters	Ensure that the character-by-character concatenation or string building handles unicode/special characters correctly according to the programming language's string implementation (e.g., UTF-8 or UTF-16).

word1 is null

How to Handle:

Return word2 if word1 is null, or an empty string if both are null to avoid NullPointerException.

word2 is null

How to Handle:

Return word1 if word2 is null, or an empty string if both are null to avoid NullPointerException.

Both word1 and word2 are empty strings

How to Handle:

Return an empty string, representing the merged result of two empty inputs.

word1 is an empty string

How to Handle:

Return word2, as there is nothing to merge from word1.

word2 is an empty string

How to Handle:

Return word1, as there is nothing to merge from word2.

Very long strings for word1 and word2

How to Handle:

The solution should use StringBuilder or similar to build the merged string efficiently to avoid quadratic time complexity associated with string concatenation.

word1 and word2 are of vastly different lengths

How to Handle:

The algorithm correctly appends remaining characters of the longer string after alternating through the shorter string length, so difference in length is naturally handled.

Strings containing unicode/special characters

How to Handle: