Scale Engineer

Merge Strings Alternately

Easy
#1618Time: 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.2 companies
Patterns
Two Pointers
Data structures
String
Companies
ZohoWells Fargo

Prompt

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.

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, i for word1 and j for word2, both to 0.
  • Loop as long as both i and j are within the bounds of their respective strings.
  • Inside the loop, append word1.charAt(i) to result, then append word2.charAt(j) to result using the + operator.
  • Increment both i and j.
  • After the loop, one of the strings may have remaining characters. Append the rest of word1 (from index i) to result.
  • Append the rest of word2 (from index j) to result.
  • Return the final result string.

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.

Solutions

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();  }}

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.

← Previous

Previous problem

Next →

Next problem