Skip to main content

Two Pointer

Merge Strings Alternately

Problem Description

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.

Examples

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

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

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 it by yourself

Approach: Two Pointer Approach

When we read the problem "merge two strings alternately," the first thing that comes to mind is how we can combine the two strings into a new one, where characters from each string are alternated. The primary task is to create a new string where we pick characters one by one from both word1 and word2, starting from the first character of each.

For example, if we have word1 = "abc" and word2 = "xyz", the merged string should alternate between the two strings, resulting in "axbycz".

We begin by initializing an empty string, res, which will hold the final merged string. Next, we loop through both strings, alternating between adding characters from word1 and word2 to the result string.
For instance, we add 'a' from word1, then 'x' from word2, and continue this process until we exhaust one of the strings. If one string is longer than the other, we simply append the remaining characters from the longer string to the end of the res string.

For example, if word1 = "ab" and word2 = "pqrs", after alternating the characters, word1 will be exhausted, but word2 will still have characters left. We append "rs" from word2 to the result, producing "apbqrs".

The process can be visualized as a step-by-step alternation of characters from both strings, handling any leftover characters from the longer string once the shorter string is exhausted.

The key to solving this problem lies in using a simple loop and handling the two strings carefully, ensuring we add characters alternately and append the remaining characters from the longer string at the end.

This approach makes the merging process intuitive and straightforward.

Let's understand with an example in a detailed manner!

Example

Input: word1 = "ab", word2 = "pqrs"

Goal: Merge characters alternately from word1 and word2. If one string runs out of characters, append the remaining characters of the longer string.

Steps:

  1. Initialize Variables:
    • n = len(word1) = 2
    • m = len(word2) = 4
    • Pointers: i = 0, j = 0
    • Result: res = "" (an empty string to store the merged characters)
  3. Merge Alternately:
    • Use a while loop to process characters alternately from word1 and word2.

Iteration 1:

  • i = 0, j = 0, res = ""
  • Add word1[0] = 'a' to res: res = "a", increment i = 1
  • Add word2[0] = 'p' to res: res = "ap", increment j = 1

Iteration 2:

  • i = 1, j = 1, res = "ap"
  • Add word1[1] = 'b' to res: res = "apb", increment i = 2
  • Add word2[1] = 'q' to res: res = "apbq", increment j = 2

Iteration 3:

  • i = 2, j = 2, res = "apbq"
  • Since i = 2 (out of bounds for word1), skip adding from word1.
  • Add word2[2] = 'r' to res: res = "apbqr", increment j = 3.

Iteration 4:

  • i = 2, j = 3, res = "apbqr"
  • Since i = 2 (out of bounds for word1), skip adding from word1.
  • Add word2[3] = 's' to res: res = "apbqrs", increment j = 4.
  1. Exit the Loop:
  • i = 2, j = 4 (both pointers are now out of bounds for their respective strings).
  • The loop ends as all characters have been processed.
  1. Return Result:
  • The merged string res is "apbqrs".

Steps to Write code

Step 1: Initialize Variables

  • Create variables n, m to store the lengths of word1 and word2.
  • Create two pointers (i and j) initialized to 0 to traverse the strings.
  • Create an empty string (or appropriate container like StringBuilder or a list) to store the result.

Step 2: Traverse the Strings

  • Use a while loop to run as long as either pointer is within the bounds of its respective string (i < n or j < m).

Step 3: Append Characters Alternately

  • Inside the loop:
    1. Check if the pointer i is within bounds (i < n), and if true, append the current character of word1 to the result and increment i.
    2. Similarly, check if pointer j is within bounds (j < m), and if true, append the current character of word2 to the result and increment j.

Step 4: Return the Result

  • After the loop finishes, return the constructed result as a string (or equivalent).
Code for All Languages
C++ 
class Solution {
public:
    // Function to merge two strings alternately
    string mergeAlternately(string word1, string word2) {
        // Step 1: Initialize the sizes of both strings and two pointers i and j
        int n = word1.size(), m = word2.size(), i = 0, j = 0;
        
        // Step 2: Initialize an empty result string to store the merged result
        string res = "";
        
        // Step 3: Run a while loop as long as there are characters left in either of the strings
        while (i < n || j < m) {
            
            // Step 4: If there are still characters left in word1, add the next character to res
            if (i < n){
                res += word1[i];  // Add word1[i] to the result
                i++;              // Move the pointer i to the next character
            }
            
            // Step 5: If there are still characters left in word2, add the next character to res
            if (j < m){
                res += word2[j];  // Add word2[j] to the result
                j++;              // Move the pointer j to the next character
            }
        }
        
        // Step 6: Return the merged result string
        return res;
    }
};

Java 
class Solution {
    public String mergeAlternately(String word1, String word2) {
        // Step 1: Initialize the lengths of both strings and a StringBuilder for the result
        int n = word1.length(), m = word2.length();
        StringBuilder res = new StringBuilder();  // Using StringBuilder to efficiently append characters
        int i = 0, j = 0;  // Pointers for word1 and word2
        
        // Step 2: Run a while loop as long as there are characters left in either word1 or word2
        while (i < n || j < m) {
            
            // Step 3: If there are still characters left in word1, add the next character to the result
            if (i < n) {
                res.append(word1.charAt(i));  // Append word1[i] to the result
                i++;  // Move the pointer i to the next character
            }
            
            // Step 4: If there are still characters left in word2, add the next character to the result
            if (j < m) {
                res.append(word2.charAt(j));  // Append word2[j] to the result
                j++;  // Move the pointer j to the next character
            }
        }
        
        // Step 5: Return the merged result as a string
        return res.toString();  // Convert StringBuilder to String and return
    }
}

Python 
class Solution(object):
    def mergeAlternately(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: str
        """
        # Step 1: Initialize the lengths of both strings
        n, m = len(word1), len(word2)
        # Initialize two pointers to 0
        i, j = 0, 0
        # Initialize an empty list to store the result
        res = []
        
        # Step 2: Run the while loop as long as there are characters left in either word1 or word2
        while i < n or j < m:
            
            # Step 3: If there are still characters in word1, add the next character to the result
            if i < n:
                res.append(word1[i])  # Append word1[i] to the result list
                i += 1  # Move pointer i to the next character
            
            # Step 4: If there are still characters in word2, add the next character to the result
            if j < m:
                res.append(word2[j])  # Append word2[j] to the result list
                j += 1  # Move pointer j to the next character
        
        # Step 5: Join the list to form a string and return it
        return ''.join(res)  # Join the list elements into a single string and return it

Javascript 
/**
 * @param {string} word1
 * @param {string} word2
 * @return {string}
 */
var mergeAlternately = function(word1, word2) {
    // Step 1: Get the lengths of both input strings
    let n = word1.length, m = word2.length;
    
    // Step 2: Initialize an empty string to hold the result
    let res = '';
    
    // Step 3: Initialize two pointers, i and j, both starting at 0
    let i = 0, j = 0;
    
    // Step 4: Use a while loop to continue as long as there are characters left in either string
    while (i < n || j < m) {
        // Step 5: If there are characters left in word1, append the next character from word1 to the result
        if (i < n) {
            res += word1[i];
            i++; // Move to the next character in word1
        }
        
        // Step 6: If there are characters left in word2, append the next character from word2 to the result
        if (j < m) {
            res += word2[j];
            j++; // Move to the next character in word2
        }
    }
    
    // Step 7: Return the merged string
    return res;
};

Time Complexity: O(n+m)

1. Inputs and Operations

  • Inputs:
    • word1 has a length of n.
    • word2 has a length of m.
  • Operations:
    • The function processes each character from both strings exactly once.
    • For every character, one of two conditions is checked:
      • If there are characters left in word1, the next character is appended.
      • If there are characters left in word2, the next character is appended.

2. Number of Iterations

  • The function iterates as long as there are characters left in either string.
  • The loop runs for max(n, m) iterations because:
    • If n > m, after processing m characters alternately, the remaining n - m characters from word1 are appended directly.
    • If m > n, after processing n characters alternately, the remaining m - n characters from word2 are appended directly.

3. String Append Operation

  • Each append operation for a single character takes O(1) on average due to efficient dynamic allocation in modern string implementations.
  • Over max(n, m) iterations, the total time spent on append operations is proportional to the number of characters processed, i.e., O(n + m).

4. Total Time Complexity

  • The loop iterates max(n, m) times.
  • Each iteration appends one character, which takes O(1) time.
  • Therefore, the total time complexity is O(n + m).

Space Complexity: O(1)

1. Inputs

  • The function takes two input strings, word1 (length n) and word2 (length m).
  • Since the inputs are read-only and not modified, their memory usage does not contribute to additional space requirements.

2. Resultant String

  • A new string, res, is created to store the merged characters.
  • The total length of res is equal to the combined lengths of the input strings:
    • Length of res = n + m
    • The memory required for res is proportional to the total number of characters, which is O(n + m).

3. Auxiliary Variables

  • A few integer variables are used:
    • n and m for the lengths of word1 and word2.
    • i and j as pointers to iterate through the strings.
    • These variables occupy O(1) space.
  • No additional data structures (like arrays or hashmaps) are used.

4. Total Space Complexity

  • Memory Usage Breakdown:
    1. Input strings: Already provided, no extra memory needed.
    2. Resultant string res: O(n + m).
    3. Auxiliary variables: O(1).
  • The dominant term is the memory required for the resultant string.

Final Space Complexity: O(n + m), where n is the length of word1 and m is the length of word2

Bonus Tip

Can we use one pointer to traverse both the strings, instead of two pointers i.e. i and j?

We can use a single pointer because we just need to pick characters from both strings, one by one, in an alternating order. The pointer helps us keep track of where we are in both strings. It starts at the beginning and picks a character from word1, then from word2, and keeps alternating until one of the strings runs out of characters. After that, we just add the remaining characters from the longer string. Since we are alternating between the two strings, we don’t need two separate pointers, one pointer can handle both strings efficiently by checking if there's a character left in each string and adding it to the result.

Key Takeaways

Having learned the optimal algorithm for Merge Strings Alternately, you can now apply this algorithm to different problems. Additionally, you can attempt to solve the following problems that utilize this approach.

Merge Sorted Array

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Largest Merge Of Two Strings

You are given two strings word1 and word2. You want to construct a string merge in the following way: while either word1 or word2 are non-empty, choose one of the following options:

If word1 is non-empty, append the first character in word1 to merge and delete it from word1.

For example, if word1 = "abc" and merge = "dv", then after choosing this operation, word1 = "bc" and merge = "dva".

If word2 is non-empty, append the first character in word2 to merge and delete it from word2.

For example, if word2 = "abc" and merge = "", then after choosing this operation, word2 = "bc" and merge = "a".
Return the lexicographically largest merge you can construct.

A string a is lexicographically larger than a string b (of the same length) if in the first position where a and b differ, a has a character strictly larger than the corresponding character in b.

For example, "abcd" is lexicographically larger than "abcc" because the first position they differ is at the fourth character, and d is greater than c.