Merge Strings Alternately

NeetCode: Merge Strings Alternately · LeetCode: 1768. Merge Strings Alternately · Difficulty: Easy

You are given two strings word1 and word2. Merge them by adding letters in alternating order, starting with word1. If one string is longer than the other, append the extra letters of the longer one at the end of the merged string. Return the merged string.

Example

Text

Input:  word1 = "abc", word2 = "pqr"     Output: "apbqcr"
Input:  word1 = "ab",  word2 = "pqrs"    Output: "apbqrs"

Brute force: index loop over both strings

Convert both strings to char[] with toCharArray, then walk i from 0 to the longer length and append a[i] and b[i] whenever those indices exist. A StringBuilder is a mutable buffer for building a string, so appending is cheap (a String is immutable, and += in a loop would copy it each time). This is linear but copies both inputs into arrays.

Java

class Solution {
    public String mergeAlternately(String word1, String word2) {
        char[] a = word1.toCharArray();
        char[] b = word2.toCharArray();
        StringBuilder out = new StringBuilder();
        for (int i = 0; i < Math.max(a.length, b.length); i++) {
            if (i < a.length) {
                out.append(a[i]);
            }
            if (i < b.length) {
                out.append(b[i]);
            }
        }
        return out.toString();
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.mergeAlternately("abc", "pqr"));
        System.out.println(s.mergeAlternately("ab", "pqrs"));
        System.out.println(s.mergeAlternately("", "xyz"));
    }
}

Output

apbqcr
apbqrs
xyz

Time: O(n + m). Space: O(n + m) for the two character arrays plus the result.

Optimal: two index pointers, one pass

Keep one index per string (the "two pointers"). While both indices are inside their strings, take one letter from each in turn with charAt. When one string runs out, the other index marks exactly where its tail starts. StringBuilder.append(CharSequence, start, end) appends that tail, and the call appends nothing for the string that is used up. The inputs are not copied. A char here is a 16-bit UTF-16 code unit, which is one letter for the lowercase English letters this problem uses.

Java

class Solution {
    public String mergeAlternately(String word1, String word2) {
        int i = 0, j = 0;
        StringBuilder out = new StringBuilder(word1.length() + word2.length());
        while (i < word1.length() && j < word2.length()) {
            out.append(word1.charAt(i++));
            out.append(word2.charAt(j++));
        }
        out.append(word1, i, word1.length()); // leftover tail of word1, if any
        out.append(word2, j, word2.length()); // leftover tail of word2, if any
        return out.toString();
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.mergeAlternately("abc", "pqr"));
        System.out.println(s.mergeAlternately("ab", "pqrs"));
        System.out.println(s.mergeAlternately("", "xyz"));
    }
}

Output

apbqcr
apbqrs
xyz

Time: O(n + m). Space: O(1) extra beyond the output builder.

Both solutions are linear; the second avoids the temporary arrays.