Merge Strings Alternately

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 ith position from input string to word1 to result, and increment i.
  • Add character at jth 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.