DEV Community

Cover image for Optimizing String Concatenation with StringBuilder
Terrence Jung
Terrence Jung

Posted on

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)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(n(n1)2)=xn2 x + 2x + ... + nx = x(1 + 2 + ... + n) = x(\frac{n(n-1)}{2}) = xn^2

Therefore, concatenating strings in this matter takes O(xn2)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;
}
Enter fullscreen mode Exit fullscreen mode

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("");
}
Enter fullscreen mode Exit fullscreen mode

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

Top comments (0)