Skip to main content

Merge Strings Alternately Solution

In this tutorial, we will solve the Merge Strings Alternately problem using two different approaches: brute force and two-pointer technique. We will provide the implementation of the solution in JavaScript, TypeScript, Python, Java, and C++.

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​

Example 1:

Input: word1 = "abc", word2 = "pqr"
Output: "apbqcr"

Example 2:

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

Example 3:

Input: word1 = "abcd", word2 = "pq"
Output: "apbqcd"

Constraints​

  • 1≤word1.length,word2.length≤1001 \leq \text{word1.length}, \text{word2.length} \leq 100
  • word1 and word2 consist of lowercase English letters.

Solution for Merge Strings Alternately Problem​

Intuition and Approach​

The problem can be solved using a brute force approach or a two-pointer technique. The brute force approach directly iterates through the strings and constructs the result, while the two-pointer technique uses two pointers to merge the strings in an alternating manner.

Approach 1: Brute Force (Naive)​

The brute force approach iterates through each character of both strings and appends them alternately to the result string. If one string is exhausted before the other, the remaining characters of the longer string are appended to the result string.

Code in Different Languages​

Written by @ImmidiSivani
class Solution {
public:
string mergeAlternately(string word1, string word2) {
string result;
int i = 0, j = 0;
while (i < word1.length() && j < word2.length()) {
result += word1[i++];
result += word2[j++];
}
while (i < word1.length()) {
result += word1[i++];
}
while (j < word2.length()) {
result += word2[j++];
}
return result;
}
};

Complexity Analysis​

  • Time Complexity: O(n+m)O(n + m)
  • Space Complexity: O(n+m)O(n + m)
  • Where n is the length of word1 and m is the length of word2.
  • The time complexity is O(n+m)O(n + m) because we iterate through both strings once.
  • The space complexity is O(n+m)O(n + m) because we store the result in a new string.
  • This approach is efficient and straightforward.

Authors:

Loading...