Merge Strings Alternately

Introduction

As part of my daily blog series on coding problems, today I tackled an interesting problem from LeetCode 75: Merge Strings Alternately. This problem involves merging two strings by adding letters in alternating order. If one string is longer than the other, the additional letters are appended at the end of the merged string. Let’s delve into the problem statement, approach, and solution.

Problem Statement

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

Example 1:

Input: word1 = "abc", word2 = "pqr" Output: "apbqcr"

Example 2:

Input: word1 = "ab", word2 = "pqrs" Output: "apbqrs"

Example 3:

Input: word1 = "abcd", word2 = "pq" Output: "apbqcd"

Constraints:

• 1 <= word1.length, word2.length <= 100

• word1 and word2 consist of lowercase English letters.

Approach to Solve the Problem

The task is straightforward but requires careful handling of string lengths and efficient string concatenation. Here's a step-by-step breakdown of the approach:

1. Initialize Pointers and StringBuilder: Use two pointers to iterate through word1 and word2 and a StringBuilder to efficiently build the merged string.

2. Alternate Character Addition: Use a loop to alternately add characters from word1 and word2 to the StringBuilder.

3. Handle Remaining Characters: After the loop, append any remaining characters from the longer string to the StringBuilder.

4. Return the Merged String: Convert the StringBuilder to a string and return it.

Solution

Here’s the Java code that implements the above approach:

public static String mergeAlternately(String word1, String word2) {
    int i = 0, j = 0;
    StringBuilder sb = new StringBuilder();

    while(i < word1.length() && j < word2.length()){
        sb.append(word1.charAt(i));
        sb.append(word2.charAt(j));
        i++;
        j++;
    }

    if(i < word1.length()){
        while(i < word1.length()){
            sb.append(word1.charAt(i));
            i++;
        }
    }

    if(j < word2.length()){
        while(j < word2.length()){
            sb.append(word2.charAt(j));
            j++;
        }
    }

    return sb.toString();
}

Explanation

1. Initialization: We start with two pointers i and j set to 0, and a StringBuilder for efficient string concatenation.

2. Alternating Addition: The while loop alternates adding characters from word1 and word2 to the StringBuilder.

3. Handling Remaining Characters: After the main loop, two additional while loops ensure that any remaining characters from either string are appended to the StringBuilder.

4. Efficiency Consideration: Using StringBuilder instead of simple string concatenation (+ operator) significantly improves performance, especially for larger strings.

Conclusion

This solution efficiently merges two strings alternately and handles the cases where one string is longer than the other. This problem reinforces the importance of choosing the right data structures (like StringBuilder over String) to optimize performance.

I hope you found this explanation helpful. Stay tuned for more daily blogs on interesting problems and concepts I encounter in my learning journey!