Merge Strings Alternately
EasyPrompt
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 rExample 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 sExample 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 <= 100word1andword2consist of lowercase English letters.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves iterating through the strings and building the merged string by repeatedly concatenating characters. In languages with immutable strings like Java, this is very inefficient because each concatenation creates a new string object and copies all the characters from the old string and the new character(s).
Algorithm
- Initialize an empty string
result. - Initialize two pointers,
iforword1andjforword2, both to 0. - Loop as long as both
iandjare within the bounds of their respective strings. - Inside the loop, append
word1.charAt(i)toresult, then appendword2.charAt(j)toresultusing the+operator. - Increment both
iandj. - After the loop, one of the strings may have remaining characters. Append the rest of
word1(from indexi) toresult. - Append the rest of
word2(from indexj) toresult. - Return the final
resultstring.
Walkthrough
We initialize an empty string result. We then iterate up to the length of the shorter string, appending one character from word1 and one from word2 to result in each step. String concatenation in a loop (e.g., using the + operator in Java) is costly. Each time result = result + newChar; is executed, a new string object is created with a size larger than the previous one, and the contents of the old result and the new character are copied over. This leads to a quadratic time complexity relative to the final string length. After the main loop, we find the remaining part of the longer string and append it to the result. While simple to write, this method is not recommended.
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.charAt(i); result += word2.charAt(j); i++; j++; } // Append remaining part of word1 if (i < word1.length()) { result += word1.substring(i); } // Append remaining part of word2 if (j < word2.length()) { result += word2.substring(j); } return result; }}Complexity
Time
O((M+N)^2), where M is the length of `word1` and N is the length of `word2`. In Java, strings are immutable. Each concatenation creates a new string and copies characters. The time to create the merged string of length `k` is the sum of `1 + 2 + ... + k-1`, which is O(k^2).
Space
O((M+N)^2), where M and N are the lengths of the strings. This is due to the storage required for all the intermediate strings created during the concatenation process in the loop.
Trade-offs
Pros
Very simple and straightforward to understand and implement.
The code is short and readable for those unfamiliar with more advanced string manipulation techniques.
Cons
Highly inefficient in terms of both time and space complexity due to the nature of immutable strings in Java.
Not suitable for large strings or performance-critical code.
This approach improves upon the brute-force method by avoiding inefficient string concatenations. It directly constructs the final string in a character array of the exact required size, which is then converted to a string once at the end. This is a very efficient, low-level approach.
Algorithm
- Get the lengths of
word1andword2, let's saymandn. - Create a character array
resultof sizem + n. - Initialize three pointers:
i = 0forword1,j = 0forword2, andk = 0for theresultarray. - Loop while
i < mandj < n. - Inside the loop, place
word1.charAt(i++)atresult[k++]. - Then, place
word2.charAt(j++)atresult[k++]. - After the first loop, one of the strings might have remaining characters. Append them.
- Loop while
i < mto copy the rest ofword1:result[k++] = word1.charAt(i++). - Loop while
j < nto copy the rest ofword2:result[k++] = word2.charAt(j++). - Return a new string created from the
resultcharacter array.
Walkthrough
We first calculate the total length of the merged string (m + n) and allocate a character array result of this size. This pre-allocation avoids the overhead of dynamic resizing. We then use three index pointers: i for word1, j for word2, and k for our result array. We iterate and place characters from word1 and word2 alternately into the result array until one of the strings is fully processed. Afterward, we append the remaining characters from the longer string. Finally, a new string is created from the character array. This method is highly efficient as it involves a single pass and a single allocation for the result.
class Solution { public String mergeAlternately(String word1, String word2) { int m = word1.length(); int n = word2.length(); char[] result = new char[m + n]; int i = 0, j = 0, k = 0; // Merge until one string is exhausted while (i < m && j < n) { result[k++] = word1.charAt(i++); result[k++] = word2.charAt(j++); } // Append remaining characters of word1 while (i < m) { result[k++] = word1.charAt(i++); } // Append remaining characters of word2 while (j < n) { result[k++] = word2.charAt(j++); } return new String(result); }}Complexity
Time
O(M + N), where M and N are the lengths of the input strings. We iterate through each string exactly once to fill the character array. Creating a string from a char array also takes O(M+N) time.
Space
O(M + N). We allocate a character array of size equal to the sum of the lengths of the two input strings to store the result.
Trade-offs
Pros
Very efficient in time and space, with O(M+N) complexity.
Avoids the overhead of
StringBuilderclass methods and its internal capacity management by pre-allocating the exact memory needed.
Cons
More verbose and lower-level than using
StringBuilder.Manual index management can be slightly more error-prone.
This is the most common and idiomatic approach in Java for building strings dynamically. It combines the efficiency of a mutable character sequence with a high-level, easy-to-use API. StringBuilder handles memory management internally, making the code cleaner and less error-prone than manual array manipulation.
Algorithm
- Initialize a
StringBuildercalledresult. - Initialize a single pointer
i = 0. - Get the lengths of
word1andword2,mandn. - Loop as long as
iis less thanmoriis less thann. - Inside the loop, if
iis a valid index forword1(i.e.,i < m), appendword1.charAt(i)toresult. - Next, if
iis a valid index forword2(i.e.,i < n), appendword2.charAt(i)toresult. - Increment
i. - After the loop, return
result.toString().
Walkthrough
This approach uses a StringBuilder to construct the result. We can use a single loop that continues as long as there are characters to process in either word1 or word2. A single pointer i can track the progress through both strings. In each iteration, we check if the i-th character exists in word1 and append it. Then we do the same for word2. This elegantly handles cases where strings have different lengths. Once the loop completes, the StringBuilder contains the final merged string, which we obtain by calling toString(). For best performance, the StringBuilder can be initialized with the final capacity (word1.length() + word2.length()) to prevent reallocations.
class Solution { public String mergeAlternately(String word1, String word2) { int m = word1.length(); int n = word2.length(); StringBuilder result = new StringBuilder(m + n); int i = 0; while (i < m || i < n) { if (i < m) { result.append(word1.charAt(i)); } if (i < n) { result.append(word2.charAt(i)); } i++; } return result.toString(); }}Complexity
Time
O(M + N). We iterate through the total length of the final string once. Appending to a `StringBuilder` takes amortized O(1) time.
Space
O(M + N). The `StringBuilder` requires space proportional to the length of the final merged string.
Trade-offs
Pros
Optimal time and space complexity of O(M+N).
High-level, readable, and safe, reducing the chance of off-by-one errors.
This is the standard and recommended way to build strings from pieces in Java.
Cons
May have a very minor performance overhead compared to a pre-sized character array, though this is often negligible and optimized away by modern JVMs.
Solutions
Solution
class Solution {public String mergeAlternately(String word1, String word2) { int m = word1.length(), n = word2.length(); StringBuilder ans = new StringBuilder(); for (int i = 0; i < m || i < n; ++i) { if (i < m) { ans.append(word1.charAt(i)); } if (i < n) { ans.append(word2.charAt(i)); } } return ans.toString(); }}class Solution {public: string mergeAlternately(string word1, string word2) { int m = word1.size(), n = word2.size(); string ans; for (int i = 0; i < m || i < n; ++i) { if (i < m) ans += word1[i]; if (i < n) ans += word2[i]; } return ans; }};class Solution: def mergeAlternately(self, word1: str, word2: str) -> str: return '' . join( a + b for a, b in zip_longest(word1, word2, fillvalue=''))Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.