562. Merge Strings Alternately - Leetcode

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.

Constraints:

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

Examples

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

Input:
word1 = abcd, word2 = pq
Output: apbqrs

Input:
word1 = ab, word2 = pqrs
Output: apbqcd

Solution

1. Initialize an empty list merged to store the resulting characters.
2. Use two pointers i and j to track positions in word1 and word2.
3. Iterate through word1 and word2 simultaneously, appending characters alternately.
4. If any characters remain in word1 or word2, append them directly to the result.
5. Convert the list to a string and return the result.

Complexity Analysis

• Time Complexity: O(n + m), where n and m are the lengths of word1 and word2, respectively. We iterate through both strings once.
• Space Complexity: O(n + m), since we store the merged string in a list before joining.

Related Problems:

- Longest substring with at most two unique characters Medium
- Replace all vowels with next consonant in a given string Medium
- Find number of Distinct Permutations of a String Medium
- Infix, Postfix and Prefix Notations/Expressions Beginner
- Check if one string is a subsequence of another string. Beginner