skip to content

How do operations like substring, replace, and concat behave given that String is immutable, and what are the performance implications?

level: seniorimportance: should knowfreq 58%

answer

  1. Transforms return new String, original untouched
  2. += in a loop = O(n^2) + N garbage objects
  3. StringBuilder for loops: mutable, amortized O(n)
  4. javac optimizes single + expressions, not loops
  5. Java 7u6: substring copies chars (no parent pinning)

basics

~10 s

Every transforming method returns a brand-new String and leaves the original alone. Doing this repeatedly (e.g. building text with + in a loop) creates many throwaway objects, so use StringBuilder for heavy building.

solid answer

~50 s

Because String is immutable, substring, replace, toUpperCase, trim, concat, and + all produce a new String rather than editing in place; if no change is needed, some return the same instance (e.g. toUpperCase on already-uppercase text, or substring(0)). The performance concern is allocation churn: each transform allocates a new char/byte array and object. The classic anti-pattern is concatenating in a loop with + or +=, which is O(n^2) because each step copies the whole accumulated string into a new object. The fix is StringBuilder (mutable, amortized O(n)) — append in the loop, toString() once at the end. Note that modern JDKs since Java 7u6 give substring its own copy of the characters rather than sharing the parent's backing array, so substring no longer pins a large parent string in memory. The compiler also optimizes simple constant and single-expression + concatenations, but explicit StringBuilder is still the rule for loops.

code

java · 12 lines
java
// Anti-pattern: O(n^2), N throwaway Strings
String bad = "";
for (int i = 0; i < n; i++) bad += i + ",";

// Correct: O(n), one final String
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) sb.append(i).append(',');
String good = sb.toString();

// Each transform returns a NEW String; original unchanged
String s = "hello";
String u = s.toUpperCase();   // u = "HELLO", s still "hello"

go deeper

for a junior

Knows transforms return new strings and that StringBuilder is preferred for building.

for a middle

Can explain why += in a loop is slow and rewrite it with StringBuilder.

for a senior

Quantifies the O(n^2) churn, knows javac's single-expression optimization limits, and the Java 7u6 substring copy change.

for a principal

Weighs allocation pressure/GC impact vs immutability benefits at scale, reasons about StringConcatFactory/invokedynamic and when interning or builders matter for hot paths.

## The core behavior: new object, original untouched Every String method that 'changes' text actually **returns a new String** and leaves the receiver unchanged: ```java String s = " Hello "; String t = s.trim(); // t = "Hello"; s is still " Hello " ``` This applies to `substring`, `replace`, `toUpperCase`/`toLowerCase`, `trim`/`strip`, `concat`, and the `+` operator. As an optimization, several methods **return the same instance when no change would result** — e.g. `toUpperCase()` on already-uppercase text, `trim()` on text with no surrounding whitespace, or `substring(0)` — but you should never rely on `==` to detect that. ## The performance issue: allocation churn Each transform allocates: a new backing array plus a new `String` object. One transform is cheap; doing it repeatedly is not. ### The classic O(n^2) loop trap ```java String result = ""; for (String part : parts) { // N parts result += part; // each += builds a NEW String } ``` Step k copies the *entire* accumulated string (length proportional to k) into a new object. Summing k from 1..N gives O(n^2) total work and N throwaway objects. For large N this is dramatically slow. ### The fix: StringBuilder `StringBuilder` is a **mutable** character buffer. It appends into a growable array (doubling capacity, so appends are amortized O(1)), giving overall O(n): ```java StringBuilder sb = new StringBuilder(); for (String part : parts) { sb.append(part); // mutates the buffer in place } String result = sb.toString(); // one final String ``` Rule of thumb: any time you assemble a string in a **loop**, use `StringBuilder` (or `StringBuffer` if you genuinely need a synchronized buffer, which is rare). ## Compiler help — and its limits For a **single expression** like `"a" + x + "b"`, the javac compiler already rewrites it into efficient StringBuilder/StringConcatFactory calls, so you don't need to hand-optimize one-liners. Pure compile-time constants (`"a" + "b"`) are folded at compile time into one literal. **But** this optimization does *not* span a loop — across iterations each `+=` is a separate statement that re-creates the whole string. So the loop trap is real despite the single-expression optimization. ## The substring memory subtlety (history matters) Before Java 7u6, `substring` shared the parent's backing `char[]` and just stored an offset+length. That made substring O(1) but had a memory leak: a tiny substring of a huge string kept the *entire* huge array alive. Since **Java 7u6**, `substring` **copies** the needed characters into a fresh array — substring is now O(k) but a small substring no longer pins a large parent in memory. Senior candidates are expected to know this changed. ## Summary trade-off Immutability buys safety, sharing, and stable hashing, at the cost of allocation when transforming. The engineering discipline is: treat individual transforms as cheap, but never build strings additively in loops — reach for `StringBuilder`.

  • Why is result += x in a loop O(n^2)?
    Strings are immutable, so each += copies the whole accumulated string into a new object. Copying grows with the current length, and summing over n iterations gives quadratic total work plus n garbage objects.
  • Did substring ever cause memory leaks? What changed?
    Before Java 7u6 substring shared the parent's char[] via offset/length, so a small substring kept a huge parent array alive. Since 7u6 substring copies the characters into a fresh array, removing that leak (at O(k) cost).

saying these in an interview costs you the question

  • Using += to build strings in a loop
  • Thinking the compiler optimizes cross-iteration concatenation
  • Claiming substring still shares the parent array (pre-7u6 behavior)
  • Believing StringBuffer is needed for normal single-threaded building

context

resolving links…