Optimizing String Concatenation with StringBuilder

Assumes understanding of Big O notation. Examples are in JavaScript. Information references "Cracking the Coding Interview" by Gayle Laakmann McDowell

Imagine you want to concatenate a large number of strings together. Assuming the strings are all the same length x and there are n strings, it takes $O(x + 2x + ... + nx)$ time. On each concatenation, we create a copy of the previous string and copy over the new string. Thus, the first iteration would require copying x characters. The next iteration would require copying 2x characters, and so on.

We can actually simplify the previously stated runtime further:

$$x + 2x + ... + nx = x(1 + 2 + ... + n) = x(\frac{n(n-1)}{2}) = xn^2$$

Therefore, concatenating strings in this matter takes $O(xn^2)$ time to complete. Pretty long if you ask me. Here's the algorithm:

function joinWords(words) {
    let sentence = "";
    for (let w of words) {
        sentence = sentence + w;
    }
    return sentence;
}

StringBuilder Class

A StringBuilder class can help you avoid this long runtime. Simply, this class creates a resizable array of all the strings and copies them back to a string only when necessary.

In JavaScript, we can simply use the join method on a resizable array to copy the list of strings into a string.

function joinWords(words) {
    let sentence = [];
    for (let w of words) {
        sentence.push(w);
    }

    return sentence.join("");
}

Now, appending a string to the array takes $O(1)$ time per operation. The final step of copying the array to a single string takes $O(n)$ time, where n is the number of strings in the array.