What Is a StringBuilder? The Fix for O(n²) String Concatenation

You write a loop. It builds a string. Tests pass. The interviewer asks for the time complexity of the string concatenation and you say O(n). They ask you to think again. You look at the loop. It still looks like O(n). It isn't.

The culprit is string concatenation, and the fix is a StringBuilder. Understanding why takes about three minutes and saves you from the specific kind of trip-up where you solve the problem correctly and then accidentally tell the interviewer it runs in O(n) when it runs in O(n²).

Strings Are Immutable. And That's Your Problem.

In Java, Python, JavaScript, C#, and most other interview languages, strings are immutable. Once created, a string object cannot be changed. This is deliberate: it makes strings safe to share across threads, easy to cache, and simple to reason about.

The downside shows up the moment you try to build one piece by piece.

result = ""
for char in ["h", "e", "l", "l", "o"]:
    result += char

This looks like five appends. It is not five appends. Each += creates a brand new string in memory, copies everything from the old string into it, then adds the new character. The old string gets thrown away. You're not appending. You're cloning and extending, repeatedly, in a loop.

When you concatenate two strings of length a and b, you copy a + b characters. In a loop where the string grows by one character each iteration:

iteration 1: copy 0 + 1 = 1 character
iteration 2: copy 1 + 1 = 2 characters
iteration 3: copy 2 + 1 = 3 characters
...
iteration n: copy (n-1) + 1 = n characters

Total characters copied: 1 + 2 + 3 + ... + n = n(n+1)/2. That's O(n²), not O(n).

For small n, nobody notices. Build a 1,000-character string this way and you're doing half a million character copies. Build a 100,000-character string and you're doing 5 billion. At that point the interviewer's patience isn't the only thing running out.

The muscle memory that ends interviews. You've read about StringBuilder. You understand it. And yet.

How StringBuilder Gets to O(n)

A StringBuilder is a mutable buffer for building strings. Instead of creating a new object on every append, it maintains an internal character array and writes into it directly. When the array fills up, it doubles in size, exactly like a dynamic array. The final toString() call copies the buffer into a real string once, at the end.

Append is O(1) amortized. You're writing into an existing array, not allocating memory and copying everything. The total work to build a string of length n is O(n): n writes into the buffer, then one O(n) copy to produce the final string.

Here's the same example in Java, the language where StringBuilder shows up most explicitly in interviews:

// O(n²), don't do this
String result = "";
for (String part : parts) {
    result += part;
}

// O(n), do this
StringBuilder sb = new StringBuilder();
for (String part : parts) {
    sb.append(part);
}
String result = sb.toString();

The API is minimal. You'll use three methods: append(), toString(), and occasionally sb.charAt(i) or sb.deleteCharAt(i) if the problem requires something more surgical. That's it. You're not writing a novel with this API.

Python and JavaScript Handle It Differently

Python doesn't have a StringBuilder class. The idiomatic fix is to collect pieces in a list and join at the end:

# O(n²), each += allocates a new string
result = ""
for char in chars:
    result += char

# O(n), join does one allocation
result = "".join(chars)

str.join() accepts any iterable of strings. It calculates the total length first, allocates exactly one buffer, then fills it. One pass, one allocation. Under the hood it's doing exactly what a StringBuilder does, just without the class name to remind you.

JavaScript works the same way. Push to an array, join at the end:

// O(n²), technically, though modern engines sometimes optimize this
let result = "";
for (const char of chars) {
    result += char;
}

// O(n), explicit and reliable
const parts = [];
for (const char of chars) {
    parts.push(char);
}
const result = parts.join("");

Modern JavaScript engines (V8, SpiderMonkey) do optimize some string concatenation patterns. V8 might save you in production. The interviewer will not. Write the explicit O(n) version and explain why.

C# has StringBuilder in System.Text, identical in spirit to Java's. Go uses strings.Builder. Swift uses String.append() directly since Swift strings are value types with copy-on-write semantics, but the same principle applies: accumulate, don't allocate.

O(n) Space Either Way, But Not Identical

Building a string of length n requires O(n) space regardless of method. The StringBuilder's internal buffer also takes O(n) space. Asymptotically they're the same.

The practical difference is allocation pressure. The naive approach allocates O(n) total objects, each larger than the last, and the garbage collector has to clean all of them up. A StringBuilder allocates O(log n) times due to doubling and discards nothing until the final toString().

In most interview problems this doesn't change the space analysis. But if an interviewer asks you to reason more carefully about memory, it's the right thing to mention.

Where String Concatenation Quietly Ruins Your Complexity

String building shows up in more problems than it looks.

Reversals and rearrangements. Any time you're constructing a new string character by character, you need a builder.

def reverse_words(s: str) -> str:
    words = s.split()
    parts = []
    for i in range(len(words) - 1, -1, -1):
        parts.append(words[i])
        if i > 0:
            parts.append(" ")
    return "".join(parts)

Parsing and encoding. Problems where you scan input and emit an output string: run-length encoding, decode string, zigzag conversion.

// LeetCode 443: String Compression
public int compress(char[] chars) {
    StringBuilder sb = new StringBuilder();
    int i = 0;
    while (i < chars.length) {
        char c = chars[i];
        int count = 0;
        while (i < chars.length && chars[i] == c) {
            i++;
            count++;
        }
        sb.append(c);
        if (count > 1) sb.append(count);
    }
    // write compressed result back to chars...
}

Backtracking. You build partial strings, explore, then undo. StringBuilder's deleteCharAt() or setLength() lets you backtrack without allocating a new string on every recursive call.

void backtrack(StringBuilder current, int remaining) {
    if (remaining == 0) {
        results.add(current.toString());
        return;
    }
    current.append('(');
    backtrack(current, remaining - 1);
    current.deleteCharAt(current.length() - 1);
    // explore other branch...
}

This is cleaner than passing a new string on every recursive call, and it avoids the hidden allocation cost. Two wins for the price of knowing one class exists.

The Two Ways This Question Bites You

First, directly: "What's the time complexity of this function?" If the function has a loop with string concatenation inside, the answer is O(n²) and the fix is a builder.

Second, as a follow-up: "Can you optimize this?" You spot the concatenation, switch to a builder, explain the improvement. Straightforward once you know the pattern. But it requires actually pausing to look at what the loop body is doing, not just counting its iterations.

The most common mistake is counting loop iterations and stopping there. Ten iterations feels like O(n). But if each iteration does O(n) work, the total is O(n²). Work done per iteration matters as much as the number of iterations. The loop isn't the unit of analysis. The loop body is.

A useful habit: whenever you see += on a string inside a loop, flag it. It's not always a problem (sometimes the strings being added are short constants), but it's always worth a second look. Think of it as a yellow flag, not a red one.

When Concatenation Is Actually Fine

String concatenation is fine when you're combining a small, fixed number of strings. "Hello, " + name + "!" creates two intermediate strings. That's O(1) allocations because the number of pieces is constant, not proportional to input size. No builder needed.

The problem is always the loop. A loop body that does O(n) work, run n times, gives you O(n²) total. This is the same reason nested loops are O(n²): you're multiplying, not adding.

If you want to practice reasoning through string complexity out loud, SpaceComplexity runs voice-based mock interviews where you explain your complexity analysis as you code. It's a different skill from typing the answer, and it's the one that actually gets tested.

Quick Recap

• Strings are immutable. Concatenation creates a new string and copies everything.
• += inside a loop is O(n²). You're paying O(n) per iteration, not O(1).
• A StringBuilder maintains a mutable buffer. Append is O(1) amortized. Final string is one copy at the end.
• Python: "".join(list). JavaScript: array.push() + .join(""). Java/C#: StringBuilder. Go: strings.Builder.
• Space complexity is O(n) either way, but builders avoid garbage pressure from O(n) intermediate allocations.
• In interviews: flag any += on strings inside a loop, explain the quadratic cost, and swap in a builder.

Further Reading

• Java StringBuilder documentation
• Python str.join documentation
• MDN: String concatenation in JavaScript
• Wikipedia: String (computer science)
• Wikipedia: Immutable object