The cost of building strings

Complexity analysis Junior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
parts = [str(i) for i in range(5)]
joined = "-".join(parts)
built = ""
for p in parts:
    built += p + "-"
print(joined, built.rstrip("-") == joined)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 0-1-2-3-4 True

Right: both build the same text; join does it in one pass.

Both strings are identical; the difference is how much copying happens on the way, which matters for big inputs.

Why not the others?
  • B 0-1-2-3-4- True. join only puts the separator between items.
  • C 01234 False. The separator is '-', so it appears between digits.

30-second answer

Python strings are immutable, so s += piece creates a new string and copies the old content. Repeated in a loop that is O(n²) total characters copied in the worst case. Collect the pieces in a list and call ''.join(parts) once: O(total length). CPython sometimes optimises += in place, but you should not rely on it.

Practise saying it · 30 s. No recording, just a timer

Explain why join beats += for building strings.

Say your answer out loud, then check which of these points you covered:

  • Strings are immutable
  • += copies: O(n²) worst case
  • join once: O(n)

Deep dive

io.StringIO is another linear-time builder.

In Kotlin and Java use StringBuilder (or buildString { }) for the same reason.

f-strings and % formatting build one string at once; the issue is only repeated concatenation.

Common mistakes

  • Concatenating inside a loop over a large input.
  • Calling ''.join inside the loop instead of once at the end.

Senior take & follow-ups

Mention join as the default; it is one line and always linear.

Follow-up questions

Think of your answer first, then open the hint.

  1. Why does CPython sometimes make += fast?

    Show hint

    If the string has no other references, it can resize it in place; that is an implementation detail.

  2. What about bytes?

    Show hint

    Use bytearray or b''.join(...).

What each operation costs: Bubble Sort · Merge Sort · Binary Search

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.