algoadvance

Leetcode 1768. Merge Strings Alternately

Problem Statement

Given two strings word1 and word2, merge them by alternating the characters from word1 and word2. If one string is longer than the other, append the additional characters to the end of the merged string.

For example:

Return the merged string.

Clarifying Questions

Before we move forward, we might ask a few clarifying questions:

  1. Can the inputs be empty strings? (Assume they can be)
  2. Is there any constraint on the length of word1 and word2? (Assume constraints as per typical strings in coding problems)

Strategy

  1. Initialize a StringBuilder to build the merged string.
  2. Use two pointers, i for word1 and j for word2, to iterate over the characters of the strings.
  3. Alternate between characters from word1 and word2:
    • Append character from word1 if i is less than the length of word1.
    • Append character from word2 if j is less than the length of word2.
  4. Increment the respective pointer (i or j) after appending a character.
  5. Once all characters from both word1 and word2 are processed, return the merged string.

Code

public class MergeStringsAlternately {
    public String mergeAlternately(String word1, String word2) {
        StringBuilder mergedString = new StringBuilder();
        int i = 0, j = 0;
        // Loop until both strings are processed
        while (i < word1.length() || j < word2.length()) {
            if (i < word1.length()) {
                mergedString.append(word1.charAt(i));
                i++;
            }
            if (j < word2.length()) {
                mergedString.append(word2.charAt(j));
                j++;
            }
        }
        return mergedString.toString();
    }

    public static void main(String[] args) {
        MergeStringsAlternately merger = new MergeStringsAlternately();
        System.out.println(merger.mergeAlternately("abc", "pqr")); // Output: apbqcr
        System.out.println(merger.mergeAlternately("ab", "pqrs")); // Output: apbqrs
        System.out.println(merger.mergeAlternately("abcd", "pq")); // Output: apbqcd
    }
}

Time Complexity

The time complexity of the algorithm is O(n + m), where n is the length of word1 and m is the length of word2. This is because we are iterating through each character of both strings exactly once.

The space complexity is also O(n + m), considering the additional space used for building the final merged string stored in the StringBuilder.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI