How do you efficiently build a large String inside a loop, and what role does pre-sizing the StringBuilder's capacity play?

## The problem being solved Concatenating with `+=` in a loop is **O(n^2)** because String is immutable, so each step re-copies the entire accumulated text. The standard remedy is `StringBuilder`, a *mutable* string accumulator. ## StringBuilder mechanics Internally a `StringBuilder` holds: - a backing `char[]` buffer (its **capacity** = how many chars it can hold before it must grow), and - a `count`/length = how many chars are actually used. `append(x)` copies `x` into the unused tail of the buffer and bumps the length. No re-copy of existing characters — that's why one append is **O(length of x)**, and appending single pieces across the loop is **amortized O(1)** each, giving **O(n)** for the whole loop. ```java StringBuilder sb = new StringBuilder(); for (String part : parts) { sb.append(part); } String result = sb.toString(); // one final String built here ``` `toString()` produces the final immutable String once, at the end. ## Why and when the buffer 'grows' The default capacity of `new StringBuilder()` is **16 characters**. When you append past the current capacity, StringBuilder must **grow**: it allocates a new, larger array (the growth policy is roughly *double the old capacity, plus a bit*), copies all existing characters into it, and discards the old array. Each individual grow is an O(current-length) copy, but because the capacity roughly *doubles* each time, the grows happen geometrically less often, and the **total** copying across all grows is still O(n) — this is the meaning of **amortized O(1)** per append. (Amortized = averaged over the whole sequence of operations; a few operations are expensive but they're rare enough that the average stays constant.) ## Pre-sizing If you can estimate the final length, pass it to the constructor: ```java StringBuilder sb = new StringBuilder(expectedLength); ``` This allocates a buffer big enough up front, so the loop performs **zero** grow-and-copy cycles and creates **zero** intermediate throwaway arrays. The asymptotic complexity is O(n) either way, but pre-sizing removes a constant-factor overhead and reduces garbage — meaningful on hot paths or very large outputs. Over-estimating wastes a little memory; under-estimating just means a few grows. A reasonable estimate (e.g. `count * averagePartLength`) is usually enough. ## Alternatives for simpler cases - `String.join(", ", list)` — when you're joining a known collection with a separator. - `list.stream().collect(Collectors.joining(", "))` — same idea in a stream pipeline (it uses a StringBuilder under the hood, often a `StringJoiner`). - These are clearer than a manual loop when you just need delimiter-separated values. ## StringBuilder vs StringBuffer `StringBuffer` is the older, **synchronized** (thread-safe) version: every method is locked. `StringBuilder` is the unsynchronized version. In the overwhelmingly common single-threaded build, the locking in `StringBuffer` buys you nothing and costs you time, so the modern default is **StringBuilder**; reach for `StringBuffer` only if the same builder is genuinely shared and mutated across multiple threads (rare — usually you'd redesign instead).