LeetCode 75 - #1 Merge Strings Alternately

After several months of not posting my side projects on LinkedIn, I realized that I have gotten used to working on large scale side projects that often never feel "done enough" to post about on LinkedIn. This combined with a desire to brush up on my DSA and JavaScript skills and the impressively consistent posting schedule of a prior coworker of mine Raymond Jones have me wanting to try some LeetCode. We'll see how long we can keep a streak.

Today's problem is LC #1768 from the LeetCode 75 study plan: Merge Strings Alternately. The goal of this problem is to take two strings (ex. "ab" and "cdef") and to merge them by adding letters in alternating order (ex. "acbdef"). Word1 is given first priority. Below is my first naive attempt at solving this problem.

/**
 * @param {string} word1
 * @param {string} word2
 * @return {string}
 */
var mergeAlternately = function(word1, word2) {
    // Get the length of the shortest word
    let minLength = Math.min(word1.length, word2.length);

    // Get the identity (1 or 2) of the longest word
    largeWord = word1;
    if (word2.length > word1.length) {
        largeWord = word2;
    }
    let mergedString = '';

    // While we're shorter than the shortest word, merge letters
    // alternately
    for (let i = 0; i < minLength; i++) {
        mergedString += word1[i];
        mergedString += word2[i];
    };

    // Merge all the remaining letters from the longest word
    if (largeWord.length > minLength) {
        mergedString += largeWord.substring(minLength);
    }

    return mergedString;
};        

A little embarrassing and rough around the edges, but I also first solved this problem in JavaScript over a year ago and I like to think I have become a much better engineer since then.

This attempt clocks in at 68ms runtime and 41MB of memory. Not terrible on the memory bit (beats 84% of submissions) but the runtime is quite slow, beating only 5% of the other submissions. This is a relatively straightforward problem without any secret sauce to make it dramatically faster, so we're going to have to do a bunch of small optimizations.

Principal Optimization: Remove Extraneous Code

I know a very smart engineer who once said that he feels most productive when deleting code. Often times in the Software Engineering community you can mark big leaps forward in the quality of a codebase by the lines of code that are now no longer needed. Lets start out deleting some code!

I'd like to remove the largeWord stuff and only have to zero in on one critical length. This can be done by realizing that for whichever word is shortest, the substring(minLength) call returns an empty string, so if word1 were the shortest

word1.substring(minLength) === ""        

This also is very quick to do compared with all the weird if statements I was doing in my original snippet. This gets us to the following code:

var mergeAlternately = function(word1, word2) {
    // Get the length of the shortest word
    let minLength = Math.min(word1.length, word2.length);
    let mergedString = '';

    // While we're shorter than the shortest word, merge letters
    // alternately
    for (let i = 0; i < minLength; i++) {
        mergedString += word1[i];
        mergedString += word2[i];
    };

    // Merge whatever characters remain
    mergedString += word1.substring(minLength);
    mergedString += word2.substring(minLength);

    return mergedString;
};        

This is already significantly faster, clocking in at 55ms thus reducing our runtime by almost 20%. The only cost was .1MB more memory, which surprisingly drops us from beating 84% of solutions memory-wise to only beating 77%, however we've jumped from beating 5% of submissions on runtime to beating 38% so that seems like an acceptable sacrifice for now.

Lets do some of those small optimizations to try and make this code faster and more memory efficient. Please note that none of the changes we will make from here on out are not good practice in a collaborative codebase, where readability is more important than knocking off 1 or 2 ms of time.

Small Optimization 1: Ternary Operator

As it turns out, replacing

let minLength = Math.min(word1.length, word2.length);        

with the ternary conditional operator

let minLength = word1.length < word2.length ? word1.length : word2.length        

earns us between 1ms and 6ms of extra speed (LeetCode's engine can take different amounts of time to process and multiple runs give different results). This is not a good idea to do in a production codebase since it's much harder to read than using the built-in Math module, but its a fun exercise in speeding up the JavaScript by about 10% in this example in the best case scenario.

Small Optimization 2: While Loop

While this is not really an optimization generally (while loops are not significantly faster than for loops in general), I have noticed while fiddling with the 30 or so iterations I made on this LeetCode problem that while loops tend to be about 1-2ms faster than for loops on LeetCode. There are lots of reasons why this might be the case, but for the sake of squeezing a few extra milliseconds out of this solution lets go ahead and swap

    for (let i = 0; i < minLength; i++) {
        mergedString += word1[i];
        mergedString += word2[i];
    };        

with

    while (i < minLength) {
        mergedString += word1[i];
        mergedString += word2[i++];
    }        

If you take a close look, you'll notice that I merged incrementing i into the last command. This is again, not good practice in a collaborative codebase, but it fits the vibe of speed coding nicely.

This gives us the following final product

/**
 * @param {string} word1
 * @param {string} word2
 * @return {string}
 */
var mergeAlternately = function(word1, word2) {
    // Get the length of the shortest word
    let minLen = word1.length < word2.length ? word1.length : word2.length
    let mergedString = '';
    let i = 0;

    // While we're shorter than the shortest word, merge letters
    // alternately
    while (i < minLen) {
        mergedString += word1[i];
        mergedString += word2[i++];
    }

    // Merge whatever characters remain
    mergedString += word1.substring(minLen) + word2.substring(minLen);

    return mergedString;
};        

This submission at its best time got 47ms beating about 84% of submissions. This means we are running a nice 30% faster than the original submission give-or-take a percent. What's really cool is, although we were focusing on optimizing for speed, this solution also has dramatically improved memory usage beating over 93% of submissions on memory usage. There are some other ways to solve this problem that get under 40ms runtime, but they all use more memory in exchange. 84/93 feels like a nice split to me, but there are many other solutions you can explore on the Solutions Page for this problem that are faster or use less memory. I will note that many of the solutions promising a 90/90 or higher ranking don't seem to hit that high anymore. It could be that there are just a lot more submissions than there were when these solutions were posted.

Post Script: One Final Optimization

One optimization that I did not mention earlier (because I started out using it) is the use of a string for our aggregator and appending to it with += rather than using an array for our aggregator and appending to it with push and then doing a join at the last minute. In a server-side environment a string is implemented as an array of characters and therefore there should be no difference in speed between the two, however modern browsers often optimize strings for append operations by modeling them as a data structure other than an array of characters. This makes appending to a string slightly faster than pushing to an array if you are running your code in a browser. Here is an interesting article I found about an alternate string data structure called a Rope that is used in the Firefox web browser to represent strings, which speeds up string concatenation significantly when compared to appending to an array.