Immutable strings and the cost of building them

In JavaScript, Python and Java, a string is immutable: once it exists, its characters can never change. Every operation that seems to change a string — upper-casing, replacing, appending — actually builds a new string and leaves the old one untouched. C++ is the exception: a std::string can be edited in place.

s = "hello"; then try s[0] = 'J'

JavaScript   s[0] = "J"   is silently ignored (a TypeError in strict mode); s is still "hello"
Python       s[0] = "J"   raises TypeError: 'str' object does not support item assignment
Java         there is no method that sets a character; s.replace(...) returns a new String
C++          s[0] = 'J';  works: s is now "Jello"

Why most languages do this

Safe sharing. Two variables can point at the same text, and neither can surprise the other by changing it.
Fast hashing. A string that can't change can compute its hash once and cache it, which makes strings excellent hash-map keys.
One copy of repeated text. Identical literals like "OK" can share one object in memory (Java calls this the string pool).
Thread safety. Several threads can read the same string with no locks.

The hidden cost of +=

Because a string can't grow, s += piece must allocate a new string and copy the whole of s into it, then the piece. Do that in a loop and the copying adds up: building a string of n characters one at a time copies 1 + 2 + 3 + … + n characters — about n² / 2. That's O(n²) for what looks like a simple loop.

Building abcd one character at a time with +=. Step 1 makes a, copying 1 character. Step 2 makes a new string ab, copying 2. Step 3 makes abc, copying 3. Step 4 makes abcd, copying 4. In total 10 characters are copied to build 4. A builder writes each character once: 4.

Some runtimes soften this — modern JavaScript engines and CPython can sometimes extend a string in place — but neither guarantees it, and Java's += in a loop really does copy each time. In an interview, assume += on a string in a loop is O(n²).

Builders: build in O(n)

The fix is the same idea in every language: collect the pieces in something that can grow cheaply, then make the final string once.

JavaScript — push pieces into an array, then parts.join("").
Python — append pieces to a list, then "".join(parts).
Java — StringBuilder: append(...) is amortized O(1), like ArrayList.add, and toString() copies once at the end.
C++ — std::string itself is the builder: s += piece and s.push_back(c) append in place, amortized O(1). (But s = s + piece still builds a full temporary copy.)

Here are both ways of joining words with single spaces. (Each language also has a one-liner — words.join(" "), " ".join(words), String.join(" ", words) — which builds in O(n) exactly like approach 2.)

Dry-run simulator

The cost of += on a string

Every += makes a whole new string. Watch the copy counter grow faster than the string.

1. Repeated +=

1function joinWords(words) {2  let s = "";3  for (let i = 0; i < words.length; i++) {4    if (i > 0) s += " ";5    s += words[i];                          // a new string each time: copies everything so far6  }7  return s;8}

JavaScript8 lines

Time O(n²), space O(n) for a result of n characters: every append copies all the characters so far.

2. A builder

1function joinWords(words) {2  const parts = [];3  for (let i = 0; i < words.length; i++) {4    if (i > 0) parts.push(" ");5    parts.push(words[i]);                   // O(1): just remember the piece6  }7  return parts.join("");                    // one pass copies each character once8}

JavaScript8 lines

Time O(n), space O(n). Each character is written into the buffer once (plus the occasional doubling of the buffer, which averages out to O(1) per character), and copied once more at the end.

Repeated +=: O(n²) time, O(n) space. Builder / join: O(n) time, O(n) space.

Changing characters in place

When a question asks you to modify a string in place — reverse it, swap characters, replace some — turn it into an array of characters first, change the array, and turn it back at the end:

JavaScript   const a = [...s];        ... a[i] = x ...   a.join("")
Python       a = list(s)              ... a[i] = x ...   "".join(a)
Java         char[] a = s.toCharArray();  ... a[i] = x ...   new String(a)
C++          s[i] = x;                (std::string is already mutable)

Converting costs O(n) once, and every change after that is O(1). Many interview questions skip this step by handing you the characters as an array already — Reverse String in the next chapter is one.

Prev Next

Was this helpful?