Problem 1768

Abstract / Summary

Alternate characters from two strings to build a new string until one ends then append the rest.

Note

The full problem description, including helpful examples, can be found on LeetCode.

C++ 1768.cpp

class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        string result;
        for (size_t i = 0; i < word1.size() || i < word2.size(); i++)
        {
            if (i < word1.size())
                result += word1[i];
            if (i < word2.size())
                result += word2[i];
        }
        return result;
    }
};
14 lines | 382 bytes | submitted August 7, 2023 | GitHub   tab size 4

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 82% (2+ million submissions).

Typical patterns to solve this problem:
  • String
  • Two Pointers
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation defines a Solution class with a single public method mergeAlternately. The method receives two std::string objects, word1 and word2, and returns a new string that interleaves characters from the two inputs. The algorithm proceeds in a single pass, appending characters from each source string in turn until both strings are exhausted.

Key Steps

The core logic can be broken down into three distinct actions: result initialization, iterative merging, and final return.

The initialization step creates an empty std::string that will accumulate the merged characters.

string result;

The iterative merging is performed by a for loop whose condition uses a logical OR to continue as long as either input still has characters at the current index. Inside the loop, two conditional blocks decide whether to append a character from each string.

for (size_t i = 0; i < word1.size() || i < word2.size(); i++)
{
    if (i < word1.size())
        result += word1[i];
    if (i < word2.size())
        result += word2[i];
}

Finally, the method returns the composed string.

return result;

Edge Cases Handled

The algorithm gracefully manages several boundary conditions without additional code paths:

  • When word1 is empty and word2 contains characters, the loop condition still evaluates true because i < word2.size() holds, and only the second conditional block executes, resulting in a copy of word2.
  • The symmetric situation where word2 is empty but word1 is not is handled by the first conditional block alone.
  • If both strings are empty, the loop condition fails immediately, leaving result empty, which is then returned.
  • When the strings have unequal lengths, the loop continues past the end of the shorter string. The conditional checks (i < word1.size() and i < word2.size()) ensure that attempts to access out-of-range indices are avoided, and the remaining characters of the longer string are appended sequentially.

Performance Optimizations

The implementation exhibits a few deliberate choices that contribute to efficient execution:

  • The loop index i is declared as size_t, matching the type returned by std::string::size(). This avoids implicit conversions and potential signed/unsigned mismatches.
  • A single for loop drives the entire merging process. By using the logical OR in the loop condition, the code eliminates the need for separate loops to handle the tail of the longer string, reducing overhead.
  • Conditional appends are performed only when the corresponding index is valid. This prevents unnecessary operations and keeps the number of character insertions to the exact count required.
  • The use of the += operator on std::string leverages the standard library’s internal buffer management, which typically grows the capacity geometrically. This amortized strategy minimizes the number of memory allocations during the construction of the result.
written by openai gpt

ELI5 - Simplified Explanation

Imagine having two different boxes of colorful alphabet blocks. The first box has some letters in a row, and the second box has some different letters in a row. The goal is to take one block from the first box and put it in a new line, then take one block from the second box and put it next to that one, and keep repeating this back and forth until all the blocks are used up.

The computer starts at the very beginning of both boxes. It looks to see if there is still a letter waiting in the first box. If it finds one, it grabs it and puts it into a new pile. Then, it checks the second box to see if a letter is waiting there. If it finds one, it grabs that too and adds it to the new pile. The computer keeps doing this over and over, jumping from one box to the other, until both boxes are completely empty. This way, the letters from both words get mixed together like they are taking turns holding hands to form one long, new word.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 26 | median = 8 | μ = 7.85 | σ = 0.72

Complexity Analysis

Time: linear
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python Java C Go Rust TS
Progiez C++ Python Java
github black-shadows C++
chandansgowda Python
charles-wangkai Java
DimitrisJim C
everthis JS
fartem Ruby
fpdjsns C++
fsq C++
haoel C++
JoshCrozier JS
Krazune C++
lkwq007 Python
suxrobGM C#
trung-hn Python
varunu28 Java
vthwang Java
yuanliu666 Kotlin
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C, C++, Go, Java, Python, Rust, TypeScript
Progiez C++, Java, Python
black-shadows C++, C++
chandansgowda Python
charles-wangkai Java
DimitrisJim C
everthis JavaScript
fartem Ruby
fpdjsns C++
fsq C++
haoel C++
JoshCrozier JavaScript
Krazune C++
lkwq007 Python
suxrobGM C#
trung-hn Python
varunu28 Java
vthwang Java
yuanliu666 Kotlin
34 links | 21 authors | 11 languages

Videos

8 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

2 similar problems

Solved On The Same Day

39 easy 31 medium 1 hard
72 solutions   August 7, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality