Strings - Merge Strings Alternately

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.

Input: word1 = "abc", word2 = "pqr"
Output: "apbqcr"
Explanation: The merged string will be merged as so:
word1 : a b c
word2 : p p r
merged: apbqcr

Input: word1 = "ab", word2 = "pqrs"
Output: "apbqrs"
Explanation: The merged string will be merged as so:
word1 : a b
word2 : p p r s
merged: apbqrs

Input: word1 = "abcd", word2 = "pq"
Output: "apbqcd"
Explanation: The merged string will be merged as so:
word1 : a b c d
word2 : p p
merged: apbqcd

Constraints:

1 <= word1.length, word2.length <= 100
word1 and word2 consist of lowercase English letters.

Solution 1 - Using two pointers

In this approach, we will use pointers to iterate through word1 and word1, and take alternative characters to form a new string.

Implementation steps:

Create three variables i to iterate through word1, j to iterate through word2, and result as StringBuilder to capture the result.
Then, loop through characters of word1 and word2, while i don't go out of bounds of word1, and j don't go out of bounds of word2:
- Add character at i^th position from input string to word1 to result, and increment i.
- Add character at j^th position from input string to word2 to result, and increment j.
At the end, we may still have left with some characters either in word1 or word2, if they are not equal length strings. Check if i did not reach the end of word1, then add remaining characters from word1 to result, and if j did not reach the end of word2, then add remaining characters from word2 to result.

public class MergeStringsAlternately { static String mergeAlternately(String word1, String word2) { int i=0; int j=0; StringBuilder result = new StringBuilder(); while(i<word1.length() && j<word2.length()) { result.append(word1.charAt(i++)); result.append(word2.charAt(j++)); } if(i<word1.length()) { // if there are any remaining characters in word1, take remaining string result.append(word1.substring(i)); } if(j<word2.length()) { result.append(word2.substring(j)); } return result.toString(); } public static void main(String[] args) { System.out.println(mergeAlternately("abc", "pqr")); System.out.println(mergeAlternately("abcd", "pq")); System.out.println(mergeAlternately("ab", "pqrs")); } }

Complexity Analysis:

Time complexity: Above code runs in O(max(m,n)) time where m is the length of input string word1 and n is the length of word2.
Space complexity: O(1) if we ignore result string, otherwise O(m +n) for the result string.

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Complexity Analysis: